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-Quelltext
1: 2:
| 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:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47:
| procedure mergesort(links,rechts:word); var stack:array of byte; mitte,richtung,stackzaehler:word; begin richtung:=0; stackzaehler:=2; stack[1]:=0; repeat mitte:=(links+rechts) div 2; if (richtung=0) and (mitte>links) then begin stack[stackzaehler]:=links; stack[succ(stackzaehler)]:=rechts; inc(stackzaehler,2); rechts:=mitte end;
if ((richtung=0) and ((mitte=links)) and (succ(mitte)<=rechts)) or (richtung=1) then begin end;
if (links=mitte) or (richtung=1) then begin if rechts<stack[pred(stackzaehler)] then begin richtung:=0; links:=succ(rechts); rechts:=stack[pred(stackzaehler)] end else begin richtung:=1; dec(stackzaehler,2); links:=stack[stackzaehler]; rechts:=stack[succ(stackzaehler)] end end until stackzaehler=0 end; |