Lisp recursive mergesort with ascending order?

Question

I'm currently trying to write a program that takes two lists of numbers assumed to already be in ascending order and mergesort them recursively.

So far I have:

(defun MERGESORT (NLIST1 NLIST2)
(cond ((null NLIST1)NLIST2)
((null NLIST2)NLIST1)
((<= (car NLIST1) (car NLIST2)) (cons(car NLIST1)(car Nlist2))
(MERGESORT(cdr NLIST1)(cdr NLIST2)))
(t(cons(car NLIST2)(car NLIST1))
(MERGESORT (cdr NLIST1)(cdr NLIST2)))))

When I write the function to the console with

(write (MERGESORT '(1 1 2 4 7) '(1 2 2 3 4 6 9)))

All I seem to output is a (6 9)

I want to get (1 1 1 2 2 2 3 4 4 6 7 9).

I might be overthinking the conditions a little and I know it's just a matter of comparing the first two elements, outputting the lesser of the two elements first and then recursing but right now I'm at a roadblock. How would you guys do this program?

Answer 1

First, this is merge, not mergesort - the arguments are already sorted.

Your code is really unreadable. With some indentation, it is

(defun MERGE (NLIST1 NLIST2)
  (cond 
   ((null NLIST1) NLIST2)
   ((null NLIST2) NLIST1)
   ((<= (car NLIST1) (car NLIST2)) 
    (cons (car NLIST1) (car Nlist2))      ; ?? no effect
    (MERGE (cdr NLIST1) (cdr NLIST2)))   
   (t
    (cons (car NLIST2) (car NLIST1))      ; ?? no effect
    (MERGE (cdr NLIST1) (cdr NLIST2))))) 

As you can see, your parentheses are just wrong. Always use indentation, to see the structure of your code better.

What it should have been, instead, is

(defun MERGE (NLIST1 NLIST2)
  (cond 
   ((null NLIST1) NLIST2)
   ((null NLIST2) NLIST1)
   ((<= (car NLIST1) (car NLIST2)) 
    (cons (car NLIST1) 
          (MERGE .... ....)))
   (t
    (cons (car NLIST2)
          (MERGE .... ....)))))