# The ArraySort interface

sorting arrays

    GENERIC INTERFACE ArraySort(Elem);

Where `Elem.T` is a type that is not an open array type and `Elem` contains

     PROCEDURE Compare(a, b: Elem.T): [-1 .. 1];

`Compare` must define a total order. Any parameter mode may be used.

    PROCEDURE Sort(VAR a: ARRAY OF Elem.T; cmp := Elem.Compare);

Sort the elements of `a` using the order defined by `cmp`.

    END ArraySort.

`Sort(a, cmp)` permutes the elements of `a` such that:

     FIRST(a) <= i < j <= LAST(a)

implies

     cmp(a[i], a[j]) <= 0.

The algorithm used is QuickSort:

- It is not stable.
- On average, it requires `O(N ln N)` comparison and assignment operations. In the worst case it may require `O(N*N)` operations.

For an expanded description of QuickSort, see [Sedgewick:Alg] .