# Sorting lists

**Author(s):**Richard A. O'Keefe (original version), The CLIP Group (changes and modifications).

This module implements some sorting list predicates.

## Usage and interface

## Documentation on exports

PREDICATE

`sort(List1,List2)`

The elements of List1 are sorted into the standard order (see Comparing terms) and any identical elements are merged, yielding List2. The time and space complexity of this operation is at worst O(N lg N) where N is the length of List1.

**General properties:** `sort(A,B)`

*If the following properties should hold at call time:*

(term_basic:= /2)term_basic:A=[1,2,6,5,2,1]*then the following properties should hold upon exit:*

(term_compare:== /2)The terms B and [1,2,5,6] are strictly identical.

`sort(A,B)`

*If the following properties hold at call time:*

(basic_props:list/1)A is a list.*then the following properties hold globally:*

(basic_props:eval/1)sort(A,B) is evaluable at compile-time.

`sort(A,B)`

*The following properties hold globally:*

(basic_props:sideff/2)sort(A,B) is side-effect free.

**Usage:**

*Description:*List2 is the sorted list corresponding to List1.*Call and exit should be compatible with:*

(basic_props:list/1)List2 is a list.*The following properties should hold at call time:*

(basic_props:list/1)List1 is a list.*The following properties should hold upon exit:*

(basic_props:list/1)List2 is a list.*The following properties should hold globally:*

(basic_props:native/1)This predicate is understood natively by CiaoPP.

PREDICATE

`keysort(List1,List2)`

List1 is sorted into order according to the value of the *keys* of its elements, yielding the list List2. No merging takes place. This predicate is *stable*, i.e., if an element `A` occurs before another element `B` *with the same key* in the input, then `A` will occur before `B` also in the output. The time and space complexity of this operation is at worst O(N lg N) where N is the length of List1.

**Usage:**

*Description:*List2 is the (key-)sorted list corresponding to List1.*Call and exit should be compatible with:*

(sort:keylist/1)List2 is a list of pairs of the form`Key-Value`.*The following properties should hold at call time:*

(sort:keylist/1)List1 is a list of pairs of the form`Key-Value`.*The following properties should hold upon exit:*

(sort:keylist/1)List2 is a list of pairs of the form`Key-Value`.*The following properties should hold globally:*

(basic_props:native/1)This predicate is understood natively by CiaoPP.

REGTYPE

**Usage:** `keypair(P)`

*Description:*P is a pair of the form "`K-_`", where`K`is considered the*key*.

## Known bugs and planned improvements

- Run-time checks have been reported not to work with this code. That means that either the assertions here, or the code that implements the run-time checks are erroneous.