Quick Sort - błędne czasy sortowania

Witam, w książce pt. "Algorytmy, struktury danych i techniki programowania" jest podany następujący algorytm Quick Sort:

void quicksort(int *tab,int left, int right)
{
  if(left<right)
 {
  int m = left;
  for(int i=left+1; i<=right; i++)
   if(tab[i] < tab[left])
     swap(tab[++m], tab[i]);
   swap(tab[m], tab[left]);
   quicksort(tab, left, m-1);
   quicksort(tab, m+1, right);
 }
}
 

gdy elementy są ułożone losowo to wszystko jest dobrze, gdy natomiast zbiór wejściowy jest już uporządkowany czas wykonania algorytmu trwa bardzo długo, tutaj dane:

czas dla losowych liczb: 0.929964
elementy zbioru wejściowego ułożone w porządku rosnącym (tak ma sortować algorytm): 30.39831
w porządku malejącym: 61.713641

czas podany w milisekundach
 

Stąd moje pytanie, dlaczego tak?

Krótka odpowiedź brzmi: bo taka jest natura quick-sorta.
Trochę dłuższa odpowiedź: pokazany algorytm bierze za punkt podziału lewy koniec, więc w przypadku zbioru już uporządkowanego zawsze dzieli dany zbiór na 2 zbiory: 0-elementowy i wszystko-elementowy. A to jest najgorszy możliwy podział dla quick-sorta i wtedy działa w O(n^2).

Co to niby za pytanie? Quick sort w przypadku pesymistycznym ma O(n²) bo w każdym obiegu "odcina" tylko jeden element (tzn dzieli tablicę na 1 element i na resztę), w efekcie na dobrą sprawę robi się z niego sortowanie proste. Dla wersji Lomuto takim przypadkiem jest tablica posortowana odwrotnie. Dla Hoara jest inaczej.

Warto posłuchać: