**Common Lisp the Language, 2nd Edition**

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 `

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.

(sortap:keys) == (sorta#'(lambda (x y) (p(sx) (sy))))

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

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

(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.

AI.Repository@cs.cmu.edu