Problem: Given two lists of elements, both monotonically nondecreasing according to some ordering predicate (optionally also given, but defaulting to `<`), 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
(lambda (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 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
(lambda (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`

created July 14, 1995
last revised June 24, 1996