Jakie sformułowanie najlepiej oddaje złożoność obliczeniową algorytmu quicksort?

Quicksort to jeden z najszybszych i najczęściej stosowanych algorytmów sortowania, ale jego złożoność obliczeniowa nie jest stała i zależy od wyboru elementu rozdzielającego (pivot). W najgorszym przypadku, gdy pivot wybierany jest niefortunnie (np. największy lub najmniejszy element), złożoność quicksort wynosi O(n²). W przypadku optymalnym (pivot dzieli zbiór na dwie równe części), złożoność to O(n log n). Algorytm ten działa w sposób rekurencyjny, dzieląc tablicę na mniejsze podzbiory, co czyni go bardzo efektywnym dla dużych zbiorów danych. W praktyce quicksort jest często szybszy niż sortowanie przez scalanie (merge sort) ze względu na mniejszą liczbę operacji przesuwania danych, mimo że oba algorytmy mają podobną średnią złożoność obliczeniową.