マージソートin LISP

資格試験の勉強中マージソートの問題が出たのでLISPで書いてみた。
アルゴリズムWikipediaを見てくだせえ
マージソート - Wikipedia


とりあえずソースはこんな感じ

(defun marge (lis1 lis2) 
  (if (null lis1) lis2 
      (if (null lis2) lis1
       (let ((top1 (first lis1))
	     (top2 (first lis2))
	     (tail1 (rest lis1))
	     (tail2 (rest lis2)))
	 (if (< top1 top2) (cons top1 (marge tail1 lis2))
	     (cons top2 (marge lis1 tail2)))
	 )
       )
      )
)

(defun get-list (lis n)
  (if (or (<= n 0) (null lis)) nil 
     (cons (first lis) (get-list (rest lis) (- n 1)))
     )
)
(defun half-list (lis f)
  (if f
      (get-list lis (floor (/ (length lis) 2)) )
      (reverse (get-list (reverse lis) (ceiling (/ (length lis) 2))))
      )
)
(defun marge-sort (lis) 
  (if (= 1 (length lis)) lis
      (let ((lis1 (half-list lis t))
	    (lis2 (half-list lis nil)))
	(marge (marge-sort lis1) (marge-sort lis2)))
      )
)

各関数の説明をすると

  1. marge(lis1 lis2):リストlis1とリストlis2を整列させて結合させる
  2. get-list(lis n):リストlisの先頭からn番目までのリストを取ってくる
  3. half-list(lis f):fが真ならリストlisの前半分を、偽なら後ろ半分を取ってくる
  4. marge-sort(lis): マージソートする

実行結果はこれ

CL-USER> (setf lis (list 2 3 5 1 2 4 7 8 4 6 7 9))
(2 3 5 1 2 4 7 8 4 6 7 9)
CL-USER> (marge-sort lis)
(1 2 2 3 4 4 5 6 7 7 8 9)

昨日に比べてエラーも少なくすんなりかけた。けどもう少しスッキリしたコードを書きたい(特にmarge)。
あとクセでLispは「(関数名 引数)」なのに「関数名(引数)」と良く書いてしまう…
何も見ずに我ながらよくやったと思う。LISPに少し慣れてきた