Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)?

[Phoenix]

Zitat von leddl:

as hat im übrigen auch bei großen Datenmengen ne bessere Laufzeit als dein Quicksort. Das hat nämlich im worst Case O(n²), MergeSort nur O(n*logn).

Im Worst-Case ja. Aber auch nur da, und versuch Du mal Daten zu konstruieren die beim Quicksort zum Worst Case führen.
Vor allem, wenn man einen geschickten randomisierten Quicksort verwendet erhält man nachweislich nie den Worst-Case.

Will heissen wir ziehen hier zum Vergleich sowieso immer nur den Average-Case heran und der ist beim Quicksort mit O(n*log(n)) nunmal nachweislich am Optimum. Deswegen heisst das Ding ja auch quicksort: Weil es der schnellste zur Zeit bekannte Sortieralgorithmus ist.