Next: System interface, Previous: Loading Programs, Up: Core library [Contents][Index]

The interface of sorting and merging API complies SRFI-95, with the following extensions:

- You can sort not only lists, vectors and strings, but
any sequence (an instance of
`<sequence>`

). - You can use both comparison procedures and comparators (see Basic comparators) to specify the order.
- You can omit comparison procedure; in that case,
elements are compared with
`default-comparator`

.

- Function:
**sort***seq :optional cmp keyfn*¶ - Function:
**sort!***seq :optional cmp keyfn*¶ [SRFI-95+] Sorts elements in a sequence

`seq`in ascending order and returns the sorted sequence.`sort!`

destructively reuses the original sequence.You can pass an instance of any

`<sequence>`

as`seq`; the same type of sequence will be returned. For`sort`

, the sequence type must have builder interface so that`sort`

can build a new sequence of the same type (See Fundamental iterator creators, for the builder interface). For`sort!`

,`seq`must be mutable.The sorting order is specified by

`cmp`

. It must be either a procedure or a comparator. If it is a procedure, it must take two elements of`seq`, and returns`#t`

if the first argument strictly precedes the second. If it is a comparator, it must have the comparison procedure. If omitted,`default-comparator`

is used.If the optional argument

`keyfn`is given, the elements are first passed to it and the results are used for comparison. It is guaranteed that`keyfn`is called at most once per element.(sort '(("Chopin" "Frederic") ("Liszt" "Franz") ("Alkan" "Charles-Valentin")) string<? car) ⇒ (("Alkan" "Charles-Valentin") ("Chopin" "Frederic") ("Liszt" "Franz"))

In the current implementation, quicksort and heapsort algorithm is used when both

`cmp`and`keyfn`is omitted, and merge sort algorithm is used otherwise. That is, the sort is stable if you pass at least`cmp`(note that to guarantee stability,`cmp`must return`#f`

when given identical arguments.) SRFI-95 requires stability, but also requires`cmp`argument, so those procedures are upper-compatible to SRFI-95.If you want to keep a sorted set of objects to which you add objects one at at time, you can also use treemaps (see Treemaps). If you only need to find out a few maximum or minimum elements instead of sorting all the elements, heaps can be used (see

`data.heap`

- Heap).

- Function:
**sorted?***seq :optional cmp keyfn*¶ [SRFI-95+] Returns

`#t`

iff elements in`seq`are in sorted order. You can pass any sequence to`seq`. The optional argument`cmp`and`keyfn`are the same as`sort`

.In SRFI-95,

`cmp`can’t be omitted.

- Function:
**merge***a b :optional cmp keyfn*¶ - Function:
**merge!***a b :optional cmp keyfn*¶ [SRFI-95+] Arguments

`a`and`b`are lists, and their elements are sorted using a compare function or a comparator`cmp`. These procedures merges two list and returns a list, whose elements are sorted using`cmp`. The destructive version`merge!`

reuses cells in`a`and`b`; the returned list is`eq?`

to either`a`or`b`.In SRFI-95,

`cmp`can’t be omitted.

The following procedures are for the backward compatibility. Their
features are already covered by extended `sort`

and `sort!`

.

- Function:
**stable-sort***seq :optional cmp keyfn*¶ - Function:
**stable-sort!***seq :optional cmp keyfn*¶ Sort a sequence

`seq`, using stable sort algorithm. Arguments`cmp`and`keyfn`are the same as`sort`

and`sort!`

.In fact,

`sort`

and`sort!`

now uses stable algorithm when`cmp`is provided, so these procedures are redundant, unless you want to omit`cmp`and yet guarantee stable sort.

- Function:
**sort-by***seq keyfn :optional cmp*¶ - Function:
**sort-by!***seq keyfn :optional cmp*¶ - Function:
**stable-sort-by***seq keyfn :optional cmp*¶ - Function:
**stable-sort-by!***seq keyfn :optional cmp*¶ Variations of sort procedures that takes a key extracting function. These are redundant now, for

`sort`

etc. takes optional`keyfn`.

Next: System interface, Previous: Loading Programs, Up: Core library [Contents][Index]

DRAFT