Next: remove; remove-if; remove-if-not; delete; delete-if; delete-if-not, Previous: concatenate, Up: Sequences

`result-type`—a `sequence`

*type specifier*.

`sequence-1`—a *sequence*.

`sequence-2`—a *sequence*.

`predicate`—a *designator* for
a *function* of two arguments that returns a *generalized boolean*.

`key`—a *designator* for a *function* of one argument,
or `nil`

.

`result-sequence`—a *proper sequence* of *type* `result-type`.

Destructively merges `sequence-1` with `sequence-2` according
to an order determined by the `predicate`. `merge`

determines
the relationship between two elements by giving keys extracted from the
sequence elements to the `predicate`.

The first argument to the `predicate` function is an element of
`sequence-1` as returned by the `key` (if supplied);
the second argument is an element of `sequence-2` as returned by
the `key` (if supplied).
`Predicate` should return *true* if and only if its 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 `predicate` should return *false*.
`merge`

considers two elements `x`

and `y`

to be equal if
`(funcall predicate x y)`

and
`(funcall predicate y x)`

both *yield* *false*.

The argument to the `key` is the `sequence` element.
Typically, the return value of the `key`
becomes the argument to `predicate`.
If `key` is not supplied or `nil`

, the sequence element itself is used.
The `key` may be executed more than once for each *sequence* *element*,
and its side effects may occur in any order.

If `key` and `predicate` return, then the merging operation
will terminate. The result of merging two *sequences* `x`

and `y`

is a new *sequence* of type `result-type` `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`

.

If `x`

and `y`

were correctly sorted according to the
`predicate`, then `z`

will also be correctly sorted.
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 `sequence-1` will
precede those from `sequence-2` in the result.

`sequence-1` and/or `sequence-2` may be destroyed.

If the `result-type` is a *subtype* of `list`

,
the result will be a *list*.

If the `result-type` is a *subtype* of `vector`

,
then if the implementation can determine the element type specified
for the `result-type`, the element type of the resulting array
is the result of *upgrading* that element type; or, if the
implementation can determine that the element type is unspecified (or `*`

),
the element type of the resulting array is `t`

;
otherwise, an error is signaled.

(setq test1 (list 1 3 4 6 7)) (setq test2 (list 2 5 8)) (merge 'list test1 test2 #'<) → (1 2 3 4 5 6 7 8) (setq test1 (copy-seq "BOY")) (setq test2 (copy-seq :nosy")) (merge 'string test1 test2 #'char-lessp) → "BnOosYy" (setq test1 (vector ((red . 1) (blue . 4)))) (setq test2 (vector ((yellow . 2) (green . 7)))) (merge 'vector test1 test2 #'< :key #'cdr) → #((RED . 1) (YELLOW . 2) (BLUE . 4) (GREEN . 7))

(merge '(vector * 4) '(1 5) '(2 4 6) #'<) should signal an error

An error must be signaled if the `result-type` is neither
a *recognizable subtype* of `list`

,
nor a *recognizable subtype* of `vector`

.

An error of *type* `type-error`

should be signaled
if `result-type` specifies the number of elements
and the sum of the lengths of `sequence-1` and `sequence-2`
is different from that number.

sort, stable-sort, Section 3.2.1 (Compiler Terminology), Section 3.6 (Traversal Rules and Side Effects)