Lisp 递归合并排序与升序?

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