problem mit MergeSort-Code -- zu langsam

[Totti]

Delphi-Quellcode:

procedure mergeIt(Vli,Vmi,Vre: integer; var liste: array of integer);
var
  tmpArr: array of integer;
  k,IndexLi,IndexRe,IndexTmp: integer;
begin
  setlength(tmpArr,Vre-Vli+1);
  IndexLi:=Vli;
  IndexRe:=Vmi+1;
  IndexTmp:=0;
  repeat
    if liste[IndexLi] <= liste[IndexRe] then
      begin
        tmpArr[IndexTmp]:=liste[IndexLi];
        inc(IndexTmp);
        inc(IndexLi);
      end
    else
      begin
        tmpArr[IndexTmp]:=liste[IndexRe];
        inc(IndexTmp);
        inc(indexRe);
      end;
  until (IndexLi > Vmi) or (IndexRe > Vre);
  while IndexLi <= Vmi do
    begin
      tmpArr[IndexTmp]:=liste[IndexLi];
      inc(IndexTmp);
      inc(indexLi);
    end;
  while IndexRe <= Vre do
    begin
      tmpArr[IndexTmp]:=liste[IndexRe];
      inc(IndexTmp);
      inc(IndexRe);
    end;
  for k:=Vli to Vre do
    liste[k]:=tmpArr[k-Vli];
end;

Delphi-Quellcode:

procedure mergeSort(Vli,Vre: integer; var liste: array of integer); //mischSortieren
var
  mi: integer;
begin
  if Vli < Vre then
    begin
      mi:=(Vli+Vre) DIV 2;
      mergeSort(Vli,mi,liste);
      mergeSort(mi+1,Vre,liste);
      mergeIt(Vli,mi,Vre,liste);
    end;
end;

ints ist deklariert als
[delphi]ints: array[0..999999] of integer;

und aufgerufen wird die ganze chose mit
[delphi]mergeSort(0,length(ints)-1,ints);[/quote]


Das Array ist mit Zufallszahlen gefüllt.




Das läuft zwar alles und sortiert auch korrekt ... nur braucht der länger als Quicksort, ca. 3x solang. Und dies oltle glaube ich nicht der Fall sin, gel?
Wo liegt der Fehler?


Vielen Dank schonmal im Voraus!

Malte

[brechi]

vielleicht am SetLength da dus öfter aufrufst aufgrund von rekursion kanns langsam werden

[Totti]

Da dann ein festdefiniertes array nutzen?
Das muss ja theoretisch so groß sein, wie das zu sortierende Array,
praktisch die Hälfte ... hmm ... mal testen.


Edit:
Hm, dan überStacked der gleich,
weil er verstndlicherweise irre viele Arrays von ner riesigen Menge reservieren muss

[brechi]

nromaler weise brauchste für nen mergesort nur 3 arrays
2 wo du die daten aufteils und 1 wo se wieder zursammengeschrieben werden