cl:merge   scheme

;;; (cl:merge a b less?)
;;; takes two lists a and b such that (sorted? a less?) and (sorted? b less?)
;;; and returns a new list in which the elements of a and b have been stably
;;; interleaved so that (sorted? (merge a b less?) less?).
;;; Note:  this does _not_ accept arrays.  See below.
;@
(define (cl:merge a b less?)
  (cond ((null? a) b)
  ((null? b) a)
  (else (let loop ((x (car a)) (a (cdr a)) (y (car b)) (b (cdr b)))
    ;; The loop handles the merging of non-empty lists.  It has
    ;; been written this way to save testing and car/cdring.
    (if (less? y x)
        (if (null? b)
      (cons y (cons x a))
      (cons y (loop x a (car b) (cdr b))))
        ;; x <= y
        (if (null? a)
      (cons x (cons y b))
      (cons x (loop (car a) (cdr a) y b))))))))