;; merge-sorted-lons consumes two lists and produces a list.
;;
;; (merge-sorted-lons l1 l2)  assumes that both l1 and l2 are
;; sorted lists of numbers (ascending order). The function 
;; generates a single list of numbers that includes all the elements
;; from both lists, and is sorted (ascending order).
;;
;; sample usage:
;;  (merge-sorted-lons '(1 3 5 7) '(0 2 4 6))
;;

(define (merge-sorted-lons l1 l2)
  (cond
   ;; if either list is empty, the other one contains
   ;; all remaing elements (already in sorted order).
   [(empty? l1) l2]
   [(empty? l2) l1]
   ;; if l1 contains the smallest element, start with that
   ;; element in the new list, then merge everything remaining.
   [(< (first l1) (first l2))
	(cons (first l1) 
		  (merge-sorted-lons (rest l1) l2))]
   [ else
	 ;; l2 contains the smallest element.
	 (cons (first l2) 
		  (merge-sorted-lons l1 (rest l2)))]))

;; test code
;;(define even (list 0 2 4 6 8))
;;(define odd (list 1 3 5 7 9))
;;(define spread (list 1 100 200 300))

;;(merge-sorted-lons even odd) ; produces '(0  1  2  3  4  5  6  7  8  9)
;;(merge-sorted-lons odd even) ; produces '(0  1  2  3  4  5  6  7  8  9)
;;(merge-sorted-lons even empty) ; produces '(0  2  4  6  8) 
;;(merge-sorted-lons odd spread) ; prodices '(1  1  3  5  7  9  100  200  300)