<), construct a monotonically nondecreasing list
containing all the elements of both source lists.
The algorithm implemented here is a tail recursion in which three values
are passed from each call to the next: the parts of the two source lists
that have not yet been transferred to the result and the part of the result
that has been constructed so far (in reverse order, so that additions can
be made at the front). In each call, the two source lists are checked to
see whether either is yet exhausted; if so, the part of the result that has
been constructed so far is reversed and prepended to the rest of the other
source (using the reverse-it procedure shown below).
Otherwise, the first elements of the respective source lists are compared;
whichever takes precedence is transferred to the result for the next
recursive call.
(define (merge list-1 list-2 . opt)
(let ((precedes? (if (null? opt) < (car opt))))
(let loop ((source-1 list-1)
(source-2 list-2)
(so-far '()))
(cond ((null? source-1)
(reverse-it so-far source-2))
((null? source-2)
(reverse-it so-far source-1))
(else
(let ((car-1 (car source-1))
(car-2 (car source-2)))
(if (precedes? car-2 car-1)
(loop source-1
(cdr source-2)
(cons car-2 so-far))
(loop (cdr source-1)
source-2
(cons car-1 so-far)))))))))
The reverse-it procedure prepends the elements of one list
(ls) to a second list (acc) in reverse order.
This version is lightly adapted from Program 4.25 of Scheme and the art
of programming, by George Springer and Daniel P. Friedman (Cambridge,
Massachusetts: MIT Press, 1989), p. 127.
(define (reverse-it ls acc)
(if (null? ls)
acc
(reverse-it (cdr ls) (cons (car ls) acc))))
This document is available on the World Wide Web as
http://www.math.grin.edu/~stone/events/scheme-workshop/merge.html