Zipping and sorting problem

I found this code for zipping in Scheme:

(define zip
  (lambda (leftList rightList)
    (if (null? rightList) 
      leftList 
      (if (member (car rightList) leftList) 
        (zip leftList (cdr rightList)) 
        (zip (append leftList (list (car rightList))) (cdr rightLis开发者_如何学编程t)))))) 

=> (zip '(1 4) '(2 3))
   (1 4 2 3)

But I want to sort the result:

=> (zip '(1 4) '(2 3))
   (1 2 3 4)

The function you are looking for is not called zip; it's called merge. Since this is a homework problem, it would be irresponsible to provide the solution. I can only offer this:

Given two lists that are already sorted, what's the easiest way to combine them into a new list that's sorted? Well, the first thing in each list (the car of the list) is the smallest element of its own list, so by comparing them, you can know which one is the smallest of both lists. Then, use recursion to merge what remains.