マージソート習作

(defun divide-two (&optional (list) (f-list nil))
  (if (< (length f-list) (length list))
      (divide-two (cdr list) (append f-list (list (car list))))
      (cons f-list list)))

(defun do-simple-insert (list num)
  (if (not list)
      (setf list (list num))
      (if (< (car list) num)
	  (setf (cdr list) (do-simple-insert (cdr list) num))
	  (setf list (cons num list))))
  list)

(defun simple-insert-sort (list)
  (let ((ret-list))
    (dolist (x list ret-list)
      (setf ret-list (do-simple-insert ret-list x)))))

(defun merge-sort (list)
  (if (< 2 (length list))
      (let ((lst (divide-two list)))
	(setf list (append (merge-sort (car lst)) (merge-sort (cdr lst))))))
  (simple-insert-sort list))

; 結果
; * (merge-sort '(11 8 10 13 4 15 1 12 2))
;
; (1 2 4 8 10 11 12 13 15)
; * 

　結合の際のソートに単純挿入ソートを採用したのだが、どうなんだろう。自分の見た範囲では、このへんについての説明が結構曖昧で、どこら辺が正しいアルゴリズムなのかが掴みづらかった。