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]
sortsequencepredicate&key :key
stable-sortsequencepredicate&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 (funcallpredicatexy) and (funcallpredicateyx) 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")

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

[Function]
mergeresult-typesequence1sequence2predicate&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 (funcallpredicatexy) and (funcallpredicateyx) 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).

change_begin
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.
change_end

Next: Lists Up: Sequences Previous: Searching Sequences for

AI.Repository@cs.cmu.edu