QuickSort()

procedure QSORT(m,n)
//sort records Rm, ...,Rn into nondecreasing order on key K. Key
Km is arbitrarily chosen as the control key. Pointers i and j are
used to partition the subfile so that at any time Kl ≤ K, l < i
and Kl ≥ K, l > j. It is assumed that Km ≤ Kn+1//
  if m < n
     then [i ← m; j ← n + 1; K ← Km
           loop
             repeat i ← i + 1 until Ki ≥ K;
             repeat j ← j - 1 until Kj ≤ K;
             if i < j
                 then call INTERCHANGE (R(i),R(j))
                 else exit
            forever
            call INTERCHANGE (R(m),R(j))
            call QSORT (m, j - 1)
            call QSORT (j + 1, n)]
end QSORT

 function partition ( i, j: integer; pivot: keytype ): integer;
 { partitions A[i], . . . ,A[j] so keys < pivot are at the left
   and keys ³ pivot are on the right.
   Returns the beginning of the group on the right. }
   var
     l, r: integer; { cursors as described above }

     begin
(1)          l := i;
(2)          r := j;
         repeat
(3)             swap(A[l], A[r]);
   
            { now the scan phase begins }
(4)             while A[l].key < pivot do
(5)                l := l + 1;
(6)             while A[r].key > = pivot do
(7)                r := r - 1
             until
(8)             l > r;
(9)          return (l)
     end; { partition } 
 
 
Fig. 8.13. The procedure partition.

     procedure quicksort ( i, j: integer );
      { sort elements A[i], . . . ,A[j] of external array A }
      var
         pivot: keytype; { the pivot value }
         pivotindex: integer; { the index of an element of A where
            key is the pivot }
         k: integer; { beginning index for group of elements ³ pivot }
      begin
(1)      pivotindex := findpivot(i, j);

(2)      if pivotindex <> 0 then begin { do nothing if all keys are equal }
(3)               pivot := A[pivotindex].key;

(4)               k := partition(i, j, pivot);
(5)               quicksort(i, k - 1);
(6)               quicksort(k, j);
         end
      end; { quicksort }


Fig. 8.14. The procedure quicksort.