Iteratives Mergesort mit Stackemulation

[Delphi-Laie]

Eine Grundsatzdiskussion wollte und erwartete ich eigentlich nicht.

Es gibt Leute, die die Rekursion nicht mögen, auch wenn die kürzeren Quelltexte natürlich übersichtlicher (und nicht etwa schlecher lesbar, das ist etwas anderes) und damit weniger fehleranfällig sind.

Hinzu kommt, daß man jegliches Risiko des Stacküberlaufes ausschließt - auch wenn man den Stack maximiert, kann man sich bei ihm eigentlich nie sicher sein, daß er - insbesondere, weil auch andere Routinen darauf zugreifen könnten - doch überläuft. Dimensioniert man den Hilfs-/Pseudostack (Array) hingegen dynamisch während der Laufzeit des Sortierens bei Bedarfe neu, so sind Speicherüberläufe praktisch ausgeschlossen.

Letztlich ging es hier (und mir) nur darum, zu zeigen, wie man die Rekursion auch des klassischen Mergesorts beseitigt bekommt (bzw. bekommen kann).

Zitat von Satty67:

Wie stark wird den der Stack belastet? Ich bin mir MergeSort nicht richtig vertraut.

(Ist das zu OT oder hier erlaubt: Bei welcher Anforderung ist MergeSort noch ideal? Meine das MergeSort sich in jedem Gebiet einem besser geeigneten Algorithmus geschlagen geben muss, weshalb ich mich bisher auch kaum damit beschäftigt hatte. Ist keine eigene Erfahrung, nur "angelesen").

Nein, Mergesort muß sich ganz und gar nicht geschlagen geben. Mergesort hat in jedem Falle nur eine n*log(n)-Komplexität/Laufzeit (im Gegensatz zu Quicksort) und kann zudem stabil implementiert werden (im Gegensatz zu Quick- und Heapsort). Der einzige verbliebene Nachteil, daß es zusätzlichen Speicher zum Verschmelzen der schon sortierten Teilmengen benötigt, stimmt auch nicht mehr, denn auch dafür gibt es Lösungen (die ich in meinem Sortierprogramm einfügte).