Servus,
das liegt einfach daran, wie der
Quicksort aufgebaut ist. Allerdings hat er nicht immer n*log(n) sondern das nur im best bzw. avg Case im Wort-Case hat der
Quicksort n² das kommt allerdings recht selten vor, von daher wird er lieber als der merge sort benutzt, da der qs einfacher zu verstehen/implementieren ist.
Finde aber den MergeSort besser, weil er immer n*log(n) hat. Evtl. ist der Konstante Faktor beim QS etwas besser, aber der wird bei der Komplexitätsbetrachtung eh meistens ausser Acht gelassen.
Aber warum es jetzt genau n*log(n) ist, kann man auf folgender Seite unter Analyse ganz gut nachlesen.
http://www.inf.fh-flensburg.de/lang/...uick/quick.htm
