Common Lisp the Language, 2nd Edition

Next: Lists Up: Sequences Previous: Searching Sequences for

# 14.5. Sorting and Merging

These functions may destructively modify argument sequences in order to put a sequence into sorted order or to merge two already sorted sequences.

[Function]
`sort sequence predicate &key :key
``stable-sort sequence predicate &key :key`

The sequence is destructively sorted according to an order determined by the predicate. The predicate should take two arguments, and return non-`nil` if and only if the first argument is strictly less than the second (in some appropriate sense). If the first argument is greater than or equal to the second (in the appropriate sense), then the predicate should return `nil`.

The `sort` function determines the relationship between two elements by giving keys extracted from the elements to the predicate. The `:key` argument, when applied to an element, should return the key for that element. The `:key` argument defaults to the identity function, thereby making the element itself be the key.

The `:key` function should not have any side effects. A useful example of a `:key` function would be a component selector function for a `defstruct` structure, used in sorting a sequence of structures.

    (sort a p :key s)
       == (sort a #'(lambda (x y) (p (s x) (s y))))

While the above two expressions are equivalent, the first may be more efficient in some implementations for certain types of arguments. For example, an implementation may choose to apply s to each item just once, putting the resulting keys into a separate table, and then sort the parallel tables, as opposed to applying s to an item every time just before applying the predicate.

If the `:key` and predicate functions always return, then the sorting operation will always terminate, producing a sequence containing the same elements as the original sequence (that is, the result is a permutation of sequence). This is guaranteed even if the predicate does not really consistently represent a total order (in which case the elements will be scrambled in some unpredictable way, but no element will be lost). If the `:key` function consistently returns meaningful keys, and the predicate does reflect some total ordering criterion on those keys, then the elements of the result sequence will be properly sorted according to that ordering.

The sorting operation performed by `sort` is not guaranteed stable. Elements considered equal by the predicate may or may not stay in their original order. (The predicate is assumed to consider two elements x and y to be equal if `(funcall predicate x y)` and `(funcall predicate y x)` are both false.) The function `stable-sort` guarantees stability but may be slower than `sort` in some situations.

The sorting operation may be destructive in all cases. In the case of an array argument, this is accomplished by permuting the elements in place. In the case of a list, the list is destructively reordered in the same manner as for `nreverse`. Thus if the argument should not be destroyed, the user must sort a copy of the argument.

Should execution of the `:key` function or the predicate cause an error, the state of the list or array being sorted is undefined. However, if the error is corrected, the sort will, of course, proceed correctly.

Note that since sorting requires many comparisons, and thus many calls to the predicate, sorting will be much faster if the predicate is a compiled function rather than interpreted.

An example:

    (setq foovector (sort foovector #'string-lessp :key #'car))

If `foovector` contained these items before the sort

    ("Tokens" "The Lion Sleeps Tonight")
    ("Carpenters" "Close to You")
    ("Rolling Stones" "Brown Sugar")
    ("Beach Boys" "I Get Around")
    ("Mozart" "Eine Kleine Nachtmusik" (K 525))
    ("Beatles" "I Want to Hold Your Hand")

then after the sort `foovector` would contain

    ("Beach Boys" "I Get Around")
    ("Beatles" "I Want to Hold Your Hand")
    ("Carpenters" "Close to You")
    ("Mozart" "Eine Kleine Nachtmusik" (K 525))
    ("Rolling Stones" "Brown Sugar")
    ("Tokens" "The Lion Sleeps Tonight")

X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9.

[Function]
`merge result-type sequence1 sequence2 predicate &key :key`

The sequences sequence1 and sequence2 are destructively merged according to an order determined by the predicate. The result is a sequence of type result-type, which must be a subtype of `sequence`, as for the function `coerce`. The predicate should take two arguments and return non-`nil` if and only if the first argument is strictly less than the second (in some appropriate sense). If the first argument is greater than or equal to the second (in the appropriate sense), then the predicate should return `nil`.

The `merge` function determines the relationship between two elements by giving keys extracted from the elements to the predicate. The `:key` function, when applied to an element, should return the key for that element; the `:key` function defaults to the identity function, thereby making the element itself be the key.

The `:key` function should not have any side effects. A useful example of a `:key` function would be a component selector function for a `defstruct` structure, used to merge a sequence of structures.

If the `:key` and predicate functions always return, then the merging operation will always terminate. The result of merging two sequences x and y is a new sequence z, such that the length of z is the sum of the lengths of x and y, and z contains all the elements of x and y. If x1 and x2 are two elements of x, and x1 precedes x2 in x, then x1 precedes x2 in z, and similarly for elements of y. In short, z is an interleaving of x and y.

Moreover, if x and y were correctly sorted according to the predicate, then z will also be correctly sorted, as shown in this example.

    (merge 'list '(1 3 4 6 7) '(2 5 8) #'<) => (1 2 3 4 5 6 7 8)

If x or y is not so sorted then z will not be sorted, but will nevertheless be an interleaving of x and y.

The merging operation is guaranteed stable; if two or more elements are considered equal by the predicate, then the elements from sequence1 will precede those from sequence2 in the result. (The predicate is assumed to consider two elements x and y to be equal if `(funcall predicate x y)` and `(funcall predicate y x)` are both false.) For example:

    (merge 'string "BOY" "nosy" #'char-lessp) => "BnOosYy"

The result can not be `"BnoOsYy"`, `"BnOosyY"`, or `"BnoOsyY"`. The function `char-lessp` ignores case, and so considers the characters `Y` and `y` to be equal, for example; the stability property then guarantees that the character from the first argument (`Y`) must precede the one from the second argument (`y`).

X3J13 voted in June 1989 (SEQUENCE-TYPE-LENGTH) to specify that `merge` should signal an error if the sequence type specifies the number of elements and the sum of the lengths of the two sequence arguments is different.

X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9.

Next: Lists Up: Sequences Previous: Searching Sequences for