10.20 Generic Sorting—library(samsort)

This library module provides generic sorting. Exported predicates:

samsort(+RawList, -Sorted)

is given a proper list RawList and unifies Sorted with a list having exactly the same elements as RawList but in ascending order according to the standard order on terms.

merge(+List1, +List2, -Merged)

is true when Merged is the stable merge of the two given lists. If the two lists are not ordered, the merge doesn't mean a great deal. Merging is perfectly well defined when the inputs contain duplicates, and all copies of an element are preserved in the output, e.g. merge("122357", "34568", "12233455678").

samsort(:Order, +RawList, -SortedList)

is given a proper list RawList and a binary predicate Order (note that it may be an N-ary predicate with the first N-2 arguments already filled in) and unifies SortedList with a sorted version of RawList. This is only supposed to work when Orderis transitive.

merge(:Order, +List1, +List2, -Merged)

is like merge/3 except that it takes an Order predicate as its first arguments, like all the generalised ordering routines.

samkeysort(+RawList, -Sorted)

is given a proper list RawList of Key-Value pairs, and unifies Sorted with a list having exactly the same elements as RawList but in ascending order according to the standard order on the keys. samkeysort/2 is stable in the sense that the relative position of elements with the same key is maintained.

keymerge(+List1, +List2, -Merged)

is like merge/3 except that it compares only the keys of its input lists. Note that it will not work properly when Merged is already instantiated.