sort : ('a -> 'a -> bool) -> 'a list -> 'a list

SYNOPSIS

Sorts a list using a given transitive `ordering' relation.

DESCRIPTION

The call

   sort op list

where op is a transitive relation on the elements of list, will topologically sort the list, i.e. will permute it such that if x op y but not y op x then x will occur to the left of y in the sorted list. In particular if op is a total order, the list will be sorted in the usual sense of the word.

FAILURE CONDITIONS

Never fails.

EXAMPLE

A simple example is:

  # sort (<) [3; 1; 4; 1; 5; 9; 2; 6; 5; 3; 5; 8; 9; 7; 9];;
  val it : int list = [1; 1; 2; 3; 3; 4; 5; 5; 5; 6; 7; 8; 9; 9; 9]

The following example is a little more complicated, and shows how a topological sorting under the relation `is free in' can be achieved. This is actually sometimes useful to consider subterms of a term in an appropriate order:

  # sort free_in [`(x + 1) + 2`; `x + 2`; `x:num`; `x + 1`; `1`];;
  val it : term list = [`1`; `x`; `x + 1`; `x + 2`; `(x + 1) + 2`]

COMMENTS

This function uses the Quicksort algorithm internally, which has good typical-case performance and will sort topologically. However, its worst-case performance is quadratic. By contrast mergesort gives a good worst-case performance but requires a total order. Note that any comparison-based topological sorting function must have quadratic behaviour in the worst case. For an $n$-element list, there are $n (n - 1) / 2$ pairs. For any topological sorting algorithm, we can make sure the first $n (n - 1) / 2 - 1$ pairs compared are unrelated in either direction, while still leaving the option of choosing for the last pair $(a,b)$ either $a < b$ or $b < a$, eventually giving a partial order. So at least $n (n - 1) / 2$ comparisons are needed to distinguish these two partial orders correctly.

SEE ALSO

mergesort.