# Structure Listsort

(* Listsort *)
val sort : ('a * 'a -> order) -> 'a list -> 'a list
val sorted : ('a * 'a -> order) -> 'a list -> bool
val merge : ('a * 'a -> order) -> 'a list * 'a list -> 'a list
val mergeUniq : ('a * 'a -> order) -> 'a list * 'a list -> 'a list
val eqclasses : ('a * 'a -> order) -> 'a list -> 'a list list
(*
[**sort** ordr xs] sorts the list xs in nondecreasing order, using the
given ordering. Uses Richard O'Keefe's smooth applicative merge
sort.
[**sorted** ordr xs] checks that the list xs is sorted in nondecreasing
order, in the given ordering.
[**merge** ordr (xs, ys)] returns a sorted list of the elements of the
sorted lists xs and ys, preserving duplicates. Both xs and ys must
be already sorted by ordr, that is, must satisfy
sorted ordr xs andalso sorted ordr ys
Then the result satisfies
sorted ordr (merge ordr (xs, ys))
[**mergeUniq** ordr (xs, ys)] returns a sorted list of the elements of
the sorted lists xs and ys, without duplicates: no elements in the
result are EQUAL by ordr. Both xs and ys must be already sorted by
ordr.
[**eqclasses** ordr xs] returns a list [xs1, xs2, ..., xsn] of
non-empty equivalence classes of xs, obtained by sorting the list
and then grouping consecutive runs of elements that are EQUAL by ordr.
If ordr is a total order, then it holds for xi in xsi and xj in xsj:
ordr(xi, xj) = EQUAL iff i=j and
ordr(xi, xj) = LESS iff i<j and
ordr(xi, xj) = GREATER iff i>j
Thus ordr(xi, xj) = Int.compare(i, j). A list of representatives
for the equivalence classes of xs under ordering ordr can be
obtained by
List.map List.hd (eqclasses ordr xs)
*)

*Moscow ML 2.10*