Anton's Quicksort with kinematic partitioning

(* ----------------- Quicksort with Kinematic partitioning ----------------- *)
(*                         ( by Anton Shepelev )                             *)
IMPLEMENTATION MODULE KineSort;
FROM SYSTEM IMPORT ADDRESS;

PROCEDURE Partition
  ( data: ADDRESS; left, right: INTEGER; VAR op: SortOps ):INTEGER;
VAR
  midInd, l, r:     INTEGER;
  lFit, rFit, bump: BOOLEAN;
  term:             INTEGER;
BEGIN
  bump := FALSE;
  (* The confluent case of a two-element array.                         *)
  (* To save one level on invocation, handle this condittion in Sort(): *)
  IF right - left = 1 THEN
    IF op.Comp( data, right, left ) < 0 THEN op.Swap( data, left, right ); END;
    RETURN left;
  END;

  midInd := (left + right) DIV 2;
  op.Swap( data, left, midInd ); (* fix pivot location for easy access *)
  r := right + 1 ; l := left + 1 - 1;

  LOOP
    lFit := TRUE; rFit:= TRUE;

    LOOP

      IF lFit THEN
        INC( l );
        lFit := op.Comp( data, l, left ) <= 0;
        IF r - l = 1 THEN bump := TRUE; EXIT; END;
      END;

      IF rFit THEN
        DEC( r );
        rFit := op.Comp( data, r, left ) >= 0;
        IF r - l = 1 THEN bump := TRUE; EXIT; END;
      END;

      IF NOT ( lFit OR rFit ) THEN EXIT; END;

    END;

    (* for lack of bitwise operations *)
    IF lFit THEN term := 2 ELSE term := 0; END;
    IF rFit THEN INC( term ); END;

    (* nested CASE would be too cumbersome *)
    CASE term OF
      0: op.Swap( data, l, r );
         IF bump THEN RETURN l; END;          |
      1: op.Swap( data, l, r ); RETURN l - 1; |
      2: IF r = right THEN
           op.Swap( data, left, r );
           RETURN l;
         ELSE RETURN r;
         END;                                 |
      3: RETURN l;
    END;
  END;

END Partition;

PROCEDURE Sort
  ( data: ADDRESS; left: INTEGER; right: INTEGER; VAR op: SortOps );
VAR middle: INTEGER;
BEGIN
  middle := Partition( data, left, right, op );
  IF middle > left  THEN Sort( data, left,   middle, op ); END;
  INC( middle );
  IF middle < right THEN Sort( data, middle, right,  op ); END;
END Sort;

END KineSort.