Stosuje algorytmy sortowania i wyszukiwania

Dlaczego tak

Sortowanie przez scalanie zawsze dzieli tablicę na połowy i scala je w czasie liniowym, więc wykonuje ok. n log n operacji dla każdych danych. Sortowanie szybkie ma średnio złożoność O(n log n), ale przy niekorzystnym wyborze elementu osiowego, np. dla danych już posortowanych, spada do O(n²). Sortowanie bąbelkowe i przez wstawianie mają złożoność pesymistyczną O(n²).

Dlaczego tak

W pierwszym przejściu porównuje się kolejne pary: 5 > 1 — zamiana, 5 > 4 — zamiana, 5 > 2 — zamiana, 5 < 8 — bez zamiany. Liczba 5 „wypływa” w prawo aż do 8, a tablica ma postać [1, 4, 2, 5, 8]. Układ [1, 5, 4, 2, 8] to wynik pierwszego kroku sortowania przez wybieranie, które zamienia tylko najmniejszy element z pierwszym, a w pełni posortowana tablica wymaga jeszcze kolejnego przejścia.

Dlaczego tak

Każde porównanie z elementem środkowym zmniejsza przeszukiwany zakres o połowę, więc po k porównaniach zostaje ok. 1000 / 2^k elementów. Ponieważ 2¹⁰ = 1024 > 1000, wystarczy co najwyżej 10 porównań. Wartość 1000 to pesymistyczna liczba porównań wyszukiwania liniowego, a 500 — jego średnia, które dotyczą tablic nieposortowanych.