|
Beschreibung
. Das Verfahren arbeitet rekursiv nach dem Divide & Conquer - Prinzip.
. Die Folge wird rekursiv bis zur trivilaen Teilfolge der Länge 1 zerteilt (Divide).
. Diese Teilfolgen werden jeweils durch Merging vereint, die vereinten wiederum. etc. bis zur sortierten Gesamfolge (Conquer).
. Es wird ein zusätzliches Hilfsfeld Ziel von der gleichen Größe wie die zu sortierende Gesamtfolge benötigt.
Programmcode
procedure MergeSort ( var f : TArray; HighIndex : integer ) : string;
var Ziel : TArray; // Hilfsfeld zum Einsortieren für die Procedure Merge
procedure Merge ( links, mitte, rechts : integer );
var h, i, j, k : integer;
begin
i := links; // Index des linken Teilfeldes
j := mitte + 1; // Index des rechten Teilfeldes
k := links; // Index des (sortierten) Hilfsfeldes
repeat
if f[i] < f[j]
then begin ziel[k] := f[i]; inc (i); end
else begin ziel[k] := f[j]; inc (j); end;
inc (k);
until (i > mitte) or (j > rechts);
if i > mitte
then for h := j to rechts do ziel [k+h-j] := f[h]
else for h := i to mitte do ziel [k+h-i] := f[h];
for h := links to rechts do f[h] := Ziel [h]; // zurückkopieren ins Datenfeld
end; // subproc Merge
procedure rMergeSort (links, rechts : integer);
// rekursiver Teil des MergeSorts
var mitte : integer;
begin
if links < rechts
then begin
mitte := (links + rechts) div 2;
rMergeSort (links , mitte ); // sortieren des linken Teils
rMergeSort (mitte+1 , rechts); // sortieren des rechten Teils
Merge (links, mitte, rechts); // zusammenmischen der beiden Teile
end;
end; // SubProc MergeSort
begin // MergeSort
rMergeSort (0, HighIndex);
end; // MergeSort
Aufwandsabschätzung
Aufwand:
. Die Datenmenge wird in n Teile zerlegt. Dazu sind insgesamt ld(n) Rekursionsschritte notwendig.
. Im Durchschnitt werden n/2 Elemente miteinander gemischt.
Daraus folgt der Aufwand .
worst-case-Aufwand:
w.o.
Sortierdauer
Bemerkung:
Die etwas seltsame Krümmung der Graphen entsteht dadurch, daß die gemessene Zeit sehr klein ist (nicht einmal eine Sekunde) und die Datenmenge groß. Dadurch ist jede Betriebssystemaktivität wie z.B. Seitenauslagerungen zu sehen.
|
