6.6.1 Sorting of Terms

Sorting routines compare and order terms without instantiating them. Users should be careful when comparing the value of uninstantiated variables. The actual order of uninstantiated variables may change in the course of program evaluation due to variable aliasing, garbage collection, or other reasons.

sort(+L1, ?L2)

The elements of the list L1 are sorted into the standard order, and any identical (i.e. `==') elements are merged, yielding the list L2. The time to perform the sorting is $O(n log n)$ where $n$ is the length of list L1.

Examples:

                | ?- sort([3.14,X,a(X),a,2,a,X,a], L).

                L = [X,3.14,2,a,a(X)];

                no

Exceptions:

instantiation_error

Argument 1 of sort/2 is a variable or is not a proper list.

keysort(+L1, ?L2)

The list L1 must consist of elements of the form Key-Value. These elements are sorted into order according to the value of Key, yielding the list L2. The elements of list L1 are scanned from left to right. Unlike sort/2, in keysort/2 no merging of multiple occurring elements takes place. The time to perform the sorting is $O(n log n)$ where $n$ is the length of list L1. Note that the elements of L1 are sorted only according to the value of Key, not according to the value of Value. The sorting of elements in L1 is not guaranteed to be stable.

Examples:

                | ?- keysort([3-a,1-b,2-c,1-a,3-a], L).

                L = [1-b,1-a,2-c,3-a,3-a];

                no

Exceptions:

instantiation_error

L1 keysort/2 is a variable or is not a proper list.

domain_error(key_value_pair,Element)

L1 contains an element Element that is not of the form Key-Value.

parsort(+L1, +SortSpec, +ElimDupl, ?L2)

machine

parsort/4 is a very general sorting routine. The list L1 may consist of elements of any form. SortSpec is the atom asc, the atom desc, or a list of terms of the form asc(I) or desc(I) where I is an integer indicating a sort argument position. The elements of list L1 are sorted into order according to the sort specification. asc indicates ascending order based on the entire term; desc indicates descending order. For a sort specification that is a list, the individual elements indicate subfields of the source terms on which to sort. For example, a specification of [asc(1)] sorts the list in ascending order on the first subfields of the terms in the list. [desc(1),asc(2)] sorts into descending order on the first subfield and within equal first subfields into ascending order on the second subfield. The order is determined by the standard predicate compare. If ElimDupl is nonzero, merging of multiple occurring elements takes place (i.e., duplicate (whole) terms are eliminated in the output). If ElimDupl is zero, then no merging takes place. A SortSpec of [] is equivalent to ``asc''. The time to perform the sorting is $O(n log n)$ where $n$ is the length of list L1. The sorting of elements in L1 is not guaranteed to be stable. parsort/4 must be imported from module machine.

Examples:

            | ?- parsort([f(3,1),f(3,2),f(2,1),f(2,2),f(1,3),f(1,4),f(3,1)],
                 [asc(1),desc(2)],1,L). 

            L = [f(1,4),f(1,3),f(2,2),f(2,1),f(3,2),f(3,1)];

            no

Error Cases:

instantiation_error

L1 is a variable or not a proper list.