{<<<< QuickSort >>>>}
{ From: COMPLETE TURBO PASCAL by Jeff Duntemann  }
{ Scott, Foresman & Co. 1986  ISBN 0-673-18600-8 }
{ Described in section 14.4 -- Last mod 2/1/86   }

PROCEDURE QuickSort(VAR SortBuf : KeyARRAY;
                        Recs    : Integer); 
 
 
PROCEDURE KeySwap(VAR RR,SS : KeyRec); 
 
VAR 
  T : KeyRec; 
 
BEGIN 
  T := RR; 
  RR := SS; 
  SS := T 
END; 
 
 
PROCEDURE DoSort(Low, High : Integer); 
 
VAR 
  I,J   : Integer; 
  Pivot : KeyRec; 
 
BEGIN 
  { Can't sort if Low is greater than or equal to High... } 
  IF Low < High THEN 
    BEGIN 
      I := Low; 
      J := High; 
      Pivot := SortBuf[J]; 
      REPEAT 
        WHILE (I < J) AND (SortBuf[I].KeyData <= Pivot.KeyData) DO I := I + 1;
        WHILE (J > I) AND (SortBuf[J].KeyData >= Pivot.KeyData) DO J := J - 1;
        IF I < J THEN KeySwap(SortBuf[I],SortBuf[J]); 
      UNTIL I >= J; 
      KeySwap(SortBuf[I],SortBuf[High]); 
      IF (I - Low < High - I) THEN 
        BEGIN 
          DoSort(Low,I-1);    { Recursive calls to DoSort! } 
          DoSort(I+1,High) 
        END 
      ELSE 
        BEGIN 
          DoSort(I+1,High);    { Recursive calls to DoSort! } 
          DoSort(Low,I-1) 
        END 
    END 
END; 
 
 
BEGIN 
  DoSort(1,Recs); 
END;  { QuickSort } 
