マージソート

次はマージソート。マージマジ、マジーロ*1。

(progn
  (assert-equal '(1 2 3 4 5) (msort '(3 5 1 4 2)))
)

(defun msort (lst)
  (if (null lst)
      nil
    (if (= 1 (length lst))
	lst
      (let *2
	       (msort (subseq lst middle)))))))

(progn
  (assert-equal '(1 2 3 4 5) (merge '(1 3 5) '(2 4)))
)

(defun merge (lst1 lst2)
  (if (null lst1)
      lst2
    (if (null lst2)
	lst1
      (if (< (car lst1) (car lst2))
	  (cons (car lst1) (merge (cdr lst1) lst2))
	(cons (car lst2) (merge lst1 (cdr lst2)))))))

*1:マジレンジャーの変身の掛け声

*2:middle (/ (length lst) 2))) (merge (msort (subseq lst 0 middle