Haskellでマージソート(続き)

id:ha-tan:20061019:1161192205の続きです。
GHCのマージソートのソースコードを読んでみます。アルゴリズムはこんな感じ。入力されたリストの各要素を1要素のリストにして、そのリストを2つずつマージします。できたリストを再度2つずつマージして、最終的に1つのリストになるまで再帰的に繰り返します。前回説明したトップダウン的な発想のアルゴリズムとは違って、これはボトムアップ的な発想のアルゴリズムです。以下にGHCのソースコードを引用します。
ファイル: ghc-6.4.2/libraries/base/Data/List.hs

757  mergesort :: (a -> a -> Ordering) -> [a] -> [a]
758  mergesort cmp = mergesort' cmp . map wrap
759
760  mergesort' :: (a -> a -> Ordering) -> [[a]] -> [a]
761  mergesort' cmp [] = []
762  mergesort' cmp [xs] = xs
763  mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss)
764
765  merge_pairs :: (a -> a -> Ordering) -> [[a]] -> [[a]]
766  merge_pairs cmp [] = []
767  merge_pairs cmp [xs] = [xs]
768  merge_pairs cmp (xs:ys:xss) = merge cmp xs ys : merge_pairs cmp xss
769
770  merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
771  merge cmp xs [] = xs
772  merge cmp [] ys = ys
773  merge cmp (x:xs) (y:ys)
774   = case x `cmp` y of
775          GT -> y : merge cmp (x:xs)   ys
776          _  -> x : merge cmp    xs (y:ys)
777
778  wrap :: a -> [a]
779  wrap x = [x]

758行目。引数がひとつ省略されています。mergesort' cmp . map wrapは、mergesort' cmp (map wrap)と解釈します。map wrapで入力されたリストの各要素を1要素のリストにしています。
760〜763行目。mergesort'では、最終的に1つのリスト(のリスト)になるまで再帰を実行します。
765〜768行目。merge_pairsでは、リスト中の各リストを2つずつマージします。
実例を挙げてアルゴリズムの動作を記述してみます。merge_pairsを呼び出す回数がlog Nになっているのがわかります。

入力されたリスト: [12, 14, 13, 11, 10, 16, 15]
map wrap後:       [[12], [14], [13], [11], [10], [16], [15]]
merge_pairs1回目: [[12, 14], [11, 13], [10, 16], [15]]
merge_pairs2回目: [[11, 12, 13, 14], [10, 15, 16]]
merge_pairs3回目: [[10, 11, 12, 13, 14, 15, 16]]
mergesort'後:     [10, 11, 12, 13, 14, 15, 16]