6.23 Sorting and merging

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.