Quicksort - theorie

[rsplisu]

Delphi-Quellcode:

    
procedure Quick_Sort(var A: array of Integer; iLo, iHi: Integer);
var
  Lo, Hi, Mid, T: Integer; 
begin
  Lo := iLo;
  Hi := iHi;
  Mid := A[(Lo + Hi) div 2];
  repeat      
    while A[Lo] < Mid do Inc(Lo);
    while A[Hi] > Mid do Dec(Hi);
    if Lo <= Hi then
    begin
      T := A[Lo];       
      A[Lo] := A[Hi];
      A[Hi] := T;
      Inc(Lo);
      Dec(Hi);
    end;    
  until Lo > Hi;
  if Hi > iLo then Quick_Sort(A, iLo, Hi);
  if Lo < iHi then Quick_Sort(A, Lo, iHi);
end;


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

Ich soll die Zahlen sortieren:

3-7-8-1-[4]-2-6-9-5

Es wird geteilt, ich erhalte Mid=4 - Pivot-Element .
Lo=iLo=3
Hi=iHi=5

3 und 5 stehen richtig so bewegen sich die Zeiger.

Lo bekam die Zahl 7 ,die groesser als 4 ist.
Hi bekam die Zahl 2 ,die kleiner als 4 ist.

Die zahlen werden vertauscht:

3-(2)-8-1-[4]-(7)-6-9-5

Lo=8
Hi=4

Und hier liegt das Problem, ich weiss nicht wie es weiter geht:


(((
Die Zahlen 4 und 8 sollen getauscht werden:

3-2-[4]-1-(8)-7-6-9-5

Lo=1
Hi=1

So wuerde Lo und Hi den Wert 1 haben und die Sortieren wuerde stoppen. Die Zahl 1 soll aber auf die linke Seite.
)))


Ich muss irgendwo einen Fehler gemacht haben. Kann mir jemand sagen wo der Fehler liegt, ob ich alles richtig mache und mir ewentuell Tipps geben?