Einfache Mergesort Implementierung

[Klaus01]

na, vielleicht schreibsr Du mal was für ein Fehler Dein Programm hat.
Dann findet der ein oder andere besser einen Ansatz Dir zu helfen.

Hier ist ein MergeSort das Deinem recht ähnlich sieht:
Die Bezeichnungen sind anders - aber sonst ist recht gleich.

Delphi-Quellcode:

program MergeSort;

{$APPTYPE CONSOLE}

uses
  SysUtils;

const n=30;

var
zufall :array [0..n-1] of integer;
i :integer;


procedure MergeSort(var A: array of Integer);

  (* Es werden zwei sortierten Bereiche des Arrays ineinander gemergt. *)

  procedure Merge(LoL, HiL, LoR, HiR: Integer);
  var
    SA: array of Integer; // Hilfsarray: die 2 Bereiche werden hier reingemergt!
    SI: Integer;          // Index für das Hilfsarray
    IL, IR: Integer;      // Lauf-Indezes der beiden Teilbereiche
  begin
    // Initialisierung
    // Das Hilfsarray SA mit der Länge beider Bereiche
    SetLength(SA, (HiL - LoL + 1) + (HiR - LoR + 1));
    // Die Laufvariablen beginnen jeweils mit dem niederwertigen Bereichsindex.
    IL := LoL;
    IR := LoR;

    // Der eigentliche Merge-Vorgang!
    for SI := Low(SA) to High(SA) do
    begin
      // Haben beide Bereiche noch Elemente?
      if ((IL <= HiL) and (IR <= HiR)) then
      begin
        if (A[IL] < A[IR]) then
        begin
          SA[SI] := A[IL];
          Inc(IL);
        end
        else
        begin
          SA[SI] := A[IR];
          Inc(IR);
        end;
      end
      // Andernfalls: Hat der linke Bereich noch Elemente?
      else if (IL <= HiL) then
      begin
        SA[SI] := A[IL];
        Inc(IL);
      end
      // Andernfalls: Hat der rechte Bereich noch Elemente?
      else if (IR <= HiR) then
      begin
        SA[SI] := A[IR];
        Inc(IR);
      end;
      // Andernfalls: Beide Breiche sind schon abgearbeitet!
      // Dieser Fall kommt aber nicht innerhalb dieser Schleife nicht zustande!
    end;

    // Finalisierung: SA wird wieder in die zwei Bereiche zurückkopiert!
    SI := Low(SA);
    for IL := LoL to HiL do
    begin
      A[IL] := SA[SI];
      Inc(SI);
    end;
    for IR := LoR to HiR do
    begin
      A[IR] := SA[SI];
      Inc(SI);
    end;
  end;

  (* Der MergeSort mit den Bereichsgrenzen *)

  procedure MSort(Lo, Hi: Integer);
  var
    Middle: Integer;
  begin
    if (Lo < Hi) then
    begin
      Middle := (Lo + Hi) div 2;

      MSort(Lo, Middle);     // Linker Bereich wird sortiert
      MSort(Middle + 1, Hi); // Rechter Bereich wird sortiert

      // Die zwei sortierten Bereiche werden ineinander gemergt!
      Merge(Lo, Middle, Middle + 1, Hi);
    end;
  end;

begin
  MSort(Low(A), High(A));
end;

begin
  randomize;
  for i:=0 to n-1 do zufall[i]:=random(n);
  writeln('Ausgangsfeld:');
  for i:=0 to n-1 do write(zufall[i],',');
  writeln; writeln;
  mergesort(zufall);
  writeln('Sortiertes Feld:');
  for i:=0 to n-1 do write(zufall[i],',');
  readln; 
end.

Grüße
Klaus