## libm3/src/sort/ArraySort.ig

Copyright (C) 1992, Digital Equipment Corporation
All rights reserved.
See the file COPYRIGHT for a full description.

Last modified on Mon Nov  8 17:00:45 PST 1993 by mcjones
modified on Fri Feb  5 15:45:03 PST 1993 by kalsow

\index{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: \begin{itemize} \item It is not stable. \item On average, it requires O(N ln N) comparison and assignment operations. In the worst case it may require O(N*N) operations. \end{itemize}

For an expanded description of QuickSort, see \cite{Sedgewick:Alg}.