The ListMergeSort structure

The ListMergeSort structure implements the merge-sort algorithm for lists.

Synopsis

signature LIST_SORT
structure ListMergeSort : LIST_SORT

Interface

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

 val uniqueSort : ('a * 'a -> order) -> 'a list -> 'a list

 val sorted : ('a * 'a -> bool) -> 'a list -> bool

Description

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

sort gt l sorts the list l in ascending order using the "greater-than" relationship defined by gt. This sort is stable and detects initial increasing and decreasing runs and thus is linear time on ordered inputs.

val uniqueSort : ('a * 'a -> order) -> 'a list -> 'a list

uniquesort cmp l sorts the list l in ascending order using the comparison function cmp, while removing duplicate elements.

val sorted : ('a * 'a -> bool) -> 'a list -> bool

sorted gt l returns true if the list is sorted in ascending order under the greater-than relation gt.

See Also

sig-MONO_ARRAY_SORT.adoc[MONO_ARRAY_SORT], sig-ARRAY_SORT.adoc[ARRAY_SORT], The Util Library