[linux-l] [OT]: algorithmische Frage: Sort parallelisieren

Matthias Kranz matthiaskranz at gmx.de
Mi Jan 3 10:12:37 CET 2007


On Wed, 2007-01-03 at 07:11 +0000, Rocco Rutte wrote:
> Wieso ist MergeSort im Vergleich zu QuickSort schneller und besser? 
> Beide gehören zur selben Klasse, für man zeigen kann, dass es nicht mehr 
> schneller geht (die Komplexität, nicht die Implementierung).

"Schneller" und "besser" sind natürlich gefährliche Komparative.

Es ist zwar nun fast schon 15 Jahre her und meine Synapsen knallen schon
lange nicht mehr so wie früher, aber wenn mich meine grauen Zellen jetzt
nicht im Stich lassen (ein Hoch auf den Erschaffer des
Langzeitgedächtnisses), dann wollte er vielleicht sagen, dass Quicksort
im Worst Case ein O(n^2) und Mergesort O(n*log(n)) braucht?

Matthias
-- 
Matthias Kranz
Berlin/München
http://mkr.oerks.de




Mehr Informationen über die Mailingliste linux-l