9.5 Sorting Sequences

Function: cl-sort seq predicate `&key :key`

This function sorts seq into increasing order as determined by using predicate to compare pairs of elements. predicate should return true (non-`nil`) if and only if its first argument is less than (not equal to) its second argument. For example, `<` and `string-lessp` are suitable predicate functions for sorting numbers and strings, respectively; `>` would sort numbers into decreasing rather than increasing order.

This function differs from Emacs’s built-in `sort` in that it can operate on any type of sequence, not just lists. Also, it accepts a `:key` argument, which is used to preprocess data fed to the predicate function. For example,

```(setq data (cl-sort data 'string-lessp :key 'downcase))
```

sorts data, a sequence of strings, into increasing alphabetical order without regard to case. A `:key` function of `car` would be useful for sorting association lists. It should only be a simple accessor though, since it’s used heavily in the current implementation.

The `cl-sort` function is destructive; it sorts lists by actually rearranging the CDR pointers in suitable fashion.

Function: cl-stable-sort seq predicate `&key :key`

This function sorts seq stably, meaning two elements which are equal in terms of predicate are guaranteed not to be rearranged out of their original order by the sort.

In practice, `cl-sort` and `cl-stable-sort` are equivalent in Emacs Lisp because the underlying `sort` function is stable by default. However, this package reserves the right to use non-stable methods for `cl-sort` in the future.

Function: cl-merge type seq1 seq2 predicate `&key :key`

This function merges two sequences seq1 and seq2 by interleaving their elements. The result sequence, of type type (in the sense of `cl-concatenate`), has length equal to the sum of the lengths of the two input sequences. The sequences may be modified destructively. Order of elements within seq1 and seq2 is preserved in the interleaving; elements of the two sequences are compared by predicate (in the sense of `sort`) and the lesser element goes first in the result. When elements are equal, those from seq1 precede those from seq2 in the result. Thus, if seq1 and seq2 are both sorted according to predicate, then the result will be a merged sequence which is (stably) sorted according to predicate.