References: MERGE
- Problem Description:
-
The page for MERGE says
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.
If this were true for every call to the predicate, this requirement, also given on that page, could not be satisfied (because test for equality requires the argument order to be reversed):
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.
In fact, the optimal algorithm for MERGE (optimal in the sense of minimizing the number of calls to the predicate) will always call the predicate with the arguments in the reverse order (one from sequence-2 followed by one from sequence-1).