[M3devel] Dual Pivot Quicksort problem

[Martin Bishop]

I saw a post on reddit about a Dual Pivot Quicksort, and I translated 
the code from Java to Modula-3.  I have it all translated, and it 
builds, but I am having boundary issues.  Somewhere on the second pass, 
the variable m2 is getting the value -2.  Here's the code:

MODULE DualPivot;

IMPORT Insertion, Fmt;

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 := left - right;
    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);
    END;
   
    IF m1 <= left THEN
      m1 := left + 1;
    END;

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

    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 + 1);
      ELSIF arr[k] > piv2 THEN
        WHILE (k < great) AND (arr[great] > piv2) DO
          DEC(great);
        END;
        Swap(arr, k, great - 1);
       
        IF arr[k] < piv1 THEN
          Swap(arr, k, less + 1);
        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 + 1);
        ELSIF arr[k] = piv2 THEN
          Swap(arr, k, great - 1);
         
          IF arr[k] = piv1 THEN
            Swap(arr, k, less + 1);
          END;
        END;
      END;
    END;

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

BEGIN
END DualPivot.

Right now when I try to run I get:

***
*** runtime error:
***    An array subscript was out of range.
***    file "../DualPivot.m3", line 61
***

Line 61 is:  IF arr[m1] < arr[m2] THEN

Anyone see what is happening? It's probably off by 1 (or more) errors, 
but I don't see them.