Sortieralgorithmen
Suchalgorithmen
Datenstrukturen
Verschiedenes
Quellen
Dem MergeSort wird nachgesagt, daß er gegenüber dem QuickSort
zusätzlichen Speicher benötigt, und dadurch
schlechtere Performance erzielt. Dies ist auch tatschächlich der
Fall. Allerdings kann man mit ein bisschen Aufwand auch eine
``in-place'' Variante relasieren. Der grosse Vorteil des Algorithmus
ist, daß er auch im worst case eine Laufzeit von
erzielt. Hat man also genügend Speicher zur
Verfügung, so ist die Wahl des MergeSort eine gute Sache.
Der MergeSort eignet geradezu perfekt dafür auf ``verketteten Listen'' zu arbeiten. Da sich aber die Implementierung auf Arrays schwieriger gestalltet, soll hier der Schwerpunkt auf solchen Datenstrukturen liegen.
Nächste Seite: Mischen
Aufwärts: Sortieren
Vorherige Seite: Optimierung
Inhalt
