Lisp递归mergesort与升序？

Question

我目前正在尝试编写一个程序,该程序将两个数字列表假定为已按升序排列并以递归方式合并它们.

到目前为止,我有:

(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)))))

当我将功能写入控制台时

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

我似乎输出的所有是(6 9)

我想得到(1 1 1 2 2 2 3 4 4 6 7 9).

我可能会稍微过度思考条件,我知道这只是比较前两个元素的问题,首先输出两个元素中较小的一个然后递归,但现在我处于障碍中.你们怎么做这个程序？

Answer 1

首先,这merge不是mergesort- 参数已经排序.

你的代码真的不可读.有一些缩进,它是

(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))))) 

如您所见,您的括号是错误的.始终使用缩进,以更好地查看代码的结构.

相反,应该是什么

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