yuessiah/116

My school homeworks

116's Issues

clean merge sort code

usage: (merge-sort '(2 1 8 3 2 5 7 9 4 6 9))
merge 和 split-list 是尾端遞迴，
可能爆 stack 是 merge-sort 本身會是 2^n 。

(defun merge (merge-list sort1 sort2)
  (cond
   ((null sort1) (append (reverse merge-list) sort2))
   ((null sort2) (append (reverse merge-list) sort1))
   (t (let ((a1 (car sort1))
            (a2 (car sort2)))
        (if (< a1 a2)
            (merge (cons a1 merge-list)
                   (cdr sort1)
                   sort2)
          (merge (cons a2 merge-list)
                 sort1
                 (cdr sort2)))))))


(defun split-list (list1 list2)
  (if (>= (length list1)
         (length list2))
      (cons list1 list2)
    (split-list (cons (car list2) list1)
                (cdr list2))))
      
(defun merge-sort (list)
  (let ((list-length (length list)))
    (if (= list-length 1)
        list
      (let* ((pair (split-list '() list))
             (list1 (car pair))
             (list2 (cdr pair)))
        (merge (merge-sort list1)
               (merge-sort list2))))))