Beim einfachen Mergesort störte mich dessen von der Rekursion verursachte Stackbeanspruchung, und ich versuchte mithin, diese Rekursion bzw. Stackbeanspruchung zu eliminieren bzw. zu emulieren (oder zu ersetzen), und zwar mit einem schnöden Array. Mit der in R. Sedgewicks Standardwälzer vorgeschlagenen Methode, beispielhaft am Quicksort, kam ich einfach nicht weiter. Vielleicht liegt es daran, daß beim Quicksort bei der Abwärtsbewegung der Rekursion sortiert wird (top-down?), beim Mergesort hingegen erst bei der Aufwärtsbewegung derselben (bottom-up?). Wie es genau bezeichnet wird, ist mir nicht bekannt. Jedenfalls tat ich mich daran, auch für diesen Sortieralgorithmus eine stackbefreite Variante zu generieren, was mir auch nach knapp 2 Tagen endlich gelang. Dabei ist der zweite Aufruf der beiden Rekursivaufrufe
Delphi-Quellcode:
if mitte>links then mergesort(links,mitte);
if rechts>succ(mitte) then mergesort(succ(mitte),rechts);
nicht mehr offensichtlich erkennbar.
Wohlgemerkt: Es geht hier
nicht um das von Natur aus iterative sog. Natural Mergesort, bei dem anfängliche vorhandene sortiert vorliegende Teilmengen/-folgen gesucht und gefunden werden und der Algorithmus schrittweise „nach oben“ auf diesen aufbaut. Ebensowenig bedarf die iterative Stackemulation, daß die Anzahl der zu sortierenden Elemente eine Zweierpotenz sein muß (derartige Mergesortvarianten gibt es auch), denn das ist beim gewöhnlichen rekursiven Mergesort ja auch nicht der Fall.
Ich fand dazu im Internet jedenfalls nichts.
Kurzum, hier das nunmehr anscheinend fehlerfreie Resultat:
Delphi-Quellcode:
procedure mergesort(links,rechts:word);
var
stack:
array {[0..x]} of byte;
{oder word oder integer oder cardinal o.ä,
statisch oder dynamisch zu deklarieren und natürlich auch ausreichend zu dimensionieren...}
mitte,richtung,stackzaehler:word;
//Richtung: 0 bedeutet ab-, 1 bedeutet aufwärts
begin
richtung:=0;
//Richtung 0 bedeutet Ab-, Richtung 1 Aufwärtsbewegung
stackzaehler:=2;
stack[1]:=0;
//nötig wegen der Befehlszeile unten: rechts:=stack[pred(stackzaehler)]
repeat
mitte:=(links+rechts)
div 2;
if (richtung=0)
and (mitte>links)
then //neue Intervallgrenzen ermitteln
begin
//mergesort(links,mitte);
stack[stackzaehler]:=links;
stack[succ(stackzaehler)]:=rechts;
inc(stackzaehler,2);
rechts:=mitte
end;
if ((richtung=0)
and ((mitte=links))
and (succ(mitte)<=rechts))
//Sortierung 2er einzelner Elemente
or (richtung=1)
//Sortierung durch Mischen sortierter Teilmengen
then
begin
{Hier erfolgt das Verschmelzen („Mergen“) der beiden schon sortierten Teilmengen
links - mitte und succ(mitte) - rechts
mit einem Algorithmus beliebiger Wahl (z.B. in meinem Sortierkino}
end;
if (links=mitte)
or (richtung=1)
then
begin
if rechts<stack[pred(stackzaehler)]
then
begin //nach „rechts“ hinübergehen
richtung:=0;
links:=succ(rechts);
rechts:=stack[pred(stackzaehler)]
end
else
begin //wieder „auftauchen“
richtung:=1;
dec(stackzaehler,2);
links:=stack[stackzaehler];
rechts:=stack[succ(stackzaehler)]
end
end
until stackzaehler=0
end;
Edit [17.04.2011, 15:20]: Code geändert