Mergesort im Speicher ist auch bei einigen Millionen Elementen *viel viel* langsamer als Quicksort. Probierts doch einfach aus. Theorie hin oder her, Quicksort, (eventuell iterativ), ist einfach am Schnellsten, auch wenn im 'worst case' Mergesort theoretisch(!) schneller ist.
Hier einige Ergebnisse:
- Testarray mit 500000 String-Elementen (random)
Iteratives Quicksort : 1762 ms
RekursivesQuicksort : 1923 ms
Mergesort : 4487 ms
Heapsort : 4716 ms
Testarray mit 1000000 Integer-Elementen (random)
Vergleich beginnt
Iteratives Quicksort : 350 ms
RekursivesQuicksort : 291 ms
Mergesort : 1152 ms
Heapsort : 1201 ms
Testarray mit 1000000 Intger-Elementen aufsteigend
Vergleich beginnt
Iteratives Quicksort : 150 ms
RekursivesQuicksort : 200 ms
Mergesort : 932 ms
Heapsort : 891 ms
Testarray mit 1000000 Integer-Elementen absteigend
Vergleich beginnt
Iteratives Quicksort : 170 ms
RekursivesQuicksort : 100 ms
Mergesort : 952 ms
Heapsort : 891 ms
Wie war das mit dem worst-case von Quicksort vs. Mergesort?
Eine Anmerkung noch: Mergesort ist für Bänder entwickelt worden, für Speichermedien also, die nur sequentiell durchlaufen werden können. Dafür ist es aber als externes Sortierverfahren, wo die Elemente auf einer Festplatte liegen, ordendlich schnell. Der Speicherbedarf ist aber auch entsprechend.