Dnia 15.07.2015 Borneq <b...@a...hidden.pl> napisał/a:
> QSort w najgorszym przypadku jak słyszałem, ma złożoność kwadratową.
> Kiedy występuje ten najgorszy przypadek? Kiedy dane są już posortowane?
> czy też jest to jeden specyficzny porządek, na którego natrafienie jest
> trudniejsze niż wygranie w toto lotka?

Zależy nie tyle od samego posortowania, co od wyboru elementu wg którego
"dzielisz" zbiór. Jeśli "pechowo" zawsze trafisz w element największy
(lub najmniejszy) to dostajesz podział na zbiór jednoelementowy i "resztę"
(czyli nie dość że takie "pechowe typowania" sortują tak na prawdę tylko
jeden element a reszta pozostaje jak było, to jeszcze rośnie
zapotrzebowanie na pamięć stosu, bo rekurencja idzie bardzo głęboko).