Iteratives Mergesort mit Stackemulation

[Delphi-Laie]

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