Sortowanie szybkie - złożoność pesymistyczna

Dlaczego sortowanie nazywa się szybkie, skoro ma złożoność pesymistyną O(n^2)?

Ponieważ:

• teoretycznie, dla losowych danych, złożoność oczekiwana to Theta(n lg n),
• praktycznie, dla większości danych otrzymuje się powyższą złożoność oczekiwaną,
• odwołuje się do pamięci głównie sekwencyjnie, wobec czego dobrze współgra z obecnymi w nowoczesnych procesorach mechanizmami pobierania pamięci z wyprzedzeniem oraz np z typowymi pamięciami podręcznymi, wobec czego efektywna wydajność jest wyższa niż np sortowania przez kopcowanie, które niby wykonuje mniej instrukcji, ale nie odwołuje się do pamięci sekwencyjnie,

Dodam tylko że w średnim przypadku quicksort ma stałe mniejsze niż mergesort (mimo że oba są nlogn) i działa szybciej od niego.

Jeżeli boisz się owej pesymistycznej złożoności n^2, możesz (spróbować) zaimplementować sortowanie introspektywne:
http://pl.wikipedia.org/wiki/Sortowanie_introspektywne

O ile się nie mylę, to std::sort go używa.