Złożoność algorytmu QuickSort: 

Sortowanie szybkie w swojej wersji, gdzie jako klucz (pivot) wybierany jest zawsze pierwszy element tablicy, będzie miało nieoptymalną złożoność czasową w przypadku, gdy tablica wejściowa jest już posortowana. W takim scenariuszu, każde wywołanie funkcji sortującej podzieli tablicę na dwie części: pierwszy element jako pivot (który jest najmniejszy, gdyż tablica jest posortowana) i resztę tablicy. Dlatego każde rekursywne wywołanie funkcji obejmie sortowanie coraz mniejszej podtablicy o jeden element mniejszej niż poprzednia.

Złożoność czasowa:

W najgorszym przypadku złożoność czasowa dla sortowania szybkiego, kiedy pivot jest zawsze najmniejszym lub największym elementem (jak w przypadku już posortowanej tablicy), wynosi $O(n^2)$. W każdym kroku rekursji, liczba elementów w podtablicy, która wymaga sortowania, zmniejsza się o $1$, co prowadzi do wykonania około $\frac{n(n-1)}{2}$ porównań w sumie.

Złożoność pamięciowa:

W przypadku użycia rekursji w sortowaniu szybkim, głębokość stosu rekursji może osiągnąć $n$ w najgorszym przypadku, gdy każde rekursywne wywołanie funkcji obejmuje sortowanie podtablicy o jeden element mniejszej. Oznacza to złożoność pamięciową $O(n)$.

Wnioski:

Oznacza to, że choć sortowanie szybkie jest zazwyczaj bardzo wydajne i ma dobrą średnią złożoność czasową $O(nlogn)$, jego wydajność znacznie spada w przypadku niekorzystnego doboru pivota, jak w przypadku posortowanej tablicy. Aby uniknąć tego problemu, w praktycznych implementacjach sortowania szybkiego często stosuje się różne metody optymalizacji wyboru pivota, takie jak wybieranie mediany z kilku losowo wybranych elementów tablicy, co pomaga zwiększyć prawdopodobieństwo uniknięcia najgorszego scenariusza i utrzymania średniej złożoności na poziomie $O(nlogn)$.