Lispでマージソート

Lisp初心者のものです。

Lispでマージソートはどのように書けばいいのでしょうか？
結果のリストは、二つの引数リストの要素すべてを含んでいなければならず、たとえば

(marge ' (3 3 6 7) ' (2 5 8))　の答えは
(2 3 3 5 6 7 8)　です。

No.1 回答者： sakusaker7 回答日時： 2008/01/21 17:18

マージソートというか、そのマージの部分では?

> (marge ' (3 3 6 7) ' (2 5 8))　の答えは

名前も merge だし、この例だとリストは両方とも
昇順にソートされてる状態ですよね。

引数は常にソートされてる状態だと仮定していいんでしょうか?

この回答への補足

すいませんマージの部分です。
はい、引数は常にソートされている状態です。

補足日時：2008/01/21 18:58

No.2 回答者： Tacosan 回答日時： 2008/01/21 19:11

CommonLisp にはそのままずばりの merge って関数があるんだけど, これを「自分で作れ」って話ですよね? そもそも手

順を書けますか?

この回答への補足

はい、自分で作るということです。
手順的には、リストの先頭データを比較して、小さい値を選んで、それを繰り返していく、という手順を考えたのですが・・・。

補足日時：2008/01/21 19:23

No.3 ベストアンサー 回答者： Tacosan 回答日時： 2008/01/21 20:06

厳密にいうと全然足りないけどまあいいか.

まず, 2つのリスト L1, L2 がどちらも「要素を持つ」ときを考えます. L1, L2 の先頭要素はもってこれますか?
で, L1 の先頭要素の方が小さければ, これは「最終的にできるリスト」の先頭要素になることが確定します. 残りの部分は「L1 から先頭要素を除いたリスト」と L2 をマージしたリストなので, これを (再帰的に) 求めてから L1 の先頭要素を (先頭に) 追加します.
L2 の先頭要素の方が小さいときもほぼ同じなので省略.
あと, いずれかのリストが空のときにはもう一方のリストを返せばいいですね. だから, 全体としておよそ
(defun merge (x y)
(if (null x) y
(if (null y) x
(let (....) ....))))
という形になるはずです. let は使わなくてもいいんだけど多分使った方がきれい.

この回答へのお礼

なるほど、そういう手順でいけばいいわけですね。
ありがとうございました。

お礼日時：2008/01/21 20:28