MODULE DualPivot;

IMPORT Insertion, Fmt, IO;

PROCEDURE Sort(VAR arr: ARRAY OF INTEGER) =
  BEGIN
    SortFromTo(arr, 0, NUMBER(arr));
  END Sort;

PROCEDURE SortFromTo(VAR arr: ARRAY OF INTEGER; from, to: INTEGER) =
  BEGIN
    RangeCheck(NUMBER(arr), from, to);
    DualPivotSort(arr, from, to - 1, 3);
  END SortFromTo;

PROCEDURE RangeCheck(len, from, to: INTEGER) RAISES {BadArgument, IndexOutOfRange} =
  BEGIN
    IF from > to THEN
      RAISE BadArgument(Fmt.Int(from) & " > " & Fmt.Int(to) & "\n");
    END;
    IF from < 0 THEN
      RAISE IndexOutOfRange("from");
    END;
    IF to > len THEN
      RAISE IndexOutOfRange("to");
    END;
  END RangeCheck;

PROCEDURE Swap(VAR arr: ARRAY OF INTEGER; i, j: INTEGER) =
  VAR temp := arr[i];
  BEGIN
    arr[i] := arr[j];
    arr[j] := temp;
  END Swap;

PROCEDURE DualPivotSort(VAR arr: ARRAY OF INTEGER; left, right, div: INTEGER) =
  VAR 
    len := right - left;
    third := len DIV div;
    m1 := left + third;
    m2 := right - third;
    piv1: INTEGER;
    piv2: INTEGER;
    less := left + 1;
    great := right - 1;
    dist: INTEGER;

  BEGIN
    IF len < 27 THEN
      Insertion.Sort(arr);
      RETURN;
    END;

    IF m1 <= left THEN
      m1 := left + 1;
    END;

    IF m2 >= right THEN
      m2 := right - 1;
    END;

    IO.Put("DEBUG: m1 = " & Fmt.Int(m1) & " m2 = " & Fmt.Int(m2) & 
      " left = " & Fmt.Int(left) & " right = " & Fmt.Int(right) & "\n");
    IO.Put("DEBUG: len = " & Fmt.Int(len) & " third = " & Fmt.Int(third) & "\n");
    IO.Put("***\n");

    IF arr[m1] < arr[m2] THEN
      Swap(arr, m1, left);
      Swap(arr, m2, right);
    ELSE
      Swap(arr, m1, right);
      Swap(arr, m2, left);
    END;

    piv1 := arr[left];
    piv2 := arr[right];
    
    FOR k := less TO great DO
      IF arr[k] < piv1 THEN
        Swap(arr, k, less);
        INC(less);
      ELSIF arr[k] > piv2 THEN
        WHILE (k < great) AND (arr[great] > piv2) DO
          DEC(great);
        END;
        Swap(arr, k, great);
        DEC(great);
        
        IF arr[k] < piv1 THEN
          Swap(arr, k, less);
          INC(less);
        END;
      END;
    END;

    dist := great - less;

    IF dist < 13 THEN
      INC(div);
    END;

    Swap(arr, less - 1, left);
    Swap(arr, great + 1, right);
    
    DualPivotSort(arr, left, less - 2, div);
    DualPivotSort(arr, great + 2, right, div);
    
    IF (dist > len - 13) AND (piv1 # piv2) THEN
      FOR k := less TO great DO
        IF arr[k] = piv1 THEN
          Swap(arr, k, less);
          INC(less);
        ELSIF arr[k] = piv2 THEN
          Swap(arr, k, great);
          DEC(great);
          
          IF arr[k] = piv1 THEN
            Swap(arr, k, less);
            INC(less);
          END;
        END;
      END;
    END;

    IF piv1 < piv2 THEN
      DualPivotSort(arr, less, great, div);
    END;
  END DualPivotSort;

BEGIN
END DualPivot