マージソートは最悪計算量 O(n log n) の単純なソートアルゴリズムです。 2つの等しい要素がソートした後でも同じ配置であるという意味で安定です。 ここではリストに対するマージソートの典型的な関数型スタイルの実装を示します。
はじめに、リストコンストラクタ list0_nil と list0_cons の省略形を導入しましょう:
#define :: list0_cons // writing [::] for list0_cons #define cons0 list0_cons // writing [cons0] for list0_cons #define nil0 list0_nil // writing [nil0] for list0_nil
次に、与えられた2つの整列されたリストを1つの整列されたリストにマージする関数テンプレート merge を実装します:
// typedef lte (a:t@ype) = (a, a) -> bool // fun{ a:t@ype } merge ( xs: list0 a, ys: list0 a, lte: lte a ) : list0 a = ( case+ xs of | cons0 (x, xs1) => ( case+ ys of | cons0 (y, ys1) => if x lte y then cons0{a}(x, merge<a> (xs1, ys, lte)) else cons0{a}(y, merge<a> (xs, ys1, lte)) // end of [if] | nil0 () => xs ) // end of [cons0] | nil0 () => ys ) (* end of [merge] *) //
次の関数テンプレート mergesort は標準のマージソートアルゴリズムを実装しています:
fun{ a:t@ype } mergesort ( xs: list0 a, lte: lte a ) : list0 a = let // val n = list0_length<a> (xs) // fun msort ( xs: list0 a, n: int, lte: lte a ) : list0 a = if n >= 2 then split (xs, n, lte, n/2, nil0) else xs // and split ( xs: list0 a, n: int, lte: lte a, i: int, xsf: list0 a ) : list0 a = if i > 0 then let val-cons0 (x, xs) = xs in split (xs, n, lte, i-1, cons0{a}(x, xsf)) end else let val xsf = list0_reverse<a> (xsf) // make sorting stable! val xsf = msort (xsf, n/2, lte) and xs = msort (xs, n-n/2, lte) in merge<a> (xsf, xs, lte) end // end of [if] // in msort (xs, n, lte) end // end of [mergesort]
関数テンプレート merge は末尾再帰ではないことに注意してください。 merge 本体の自分自身の呼び出しが末尾呼出ではありません。 これは実際の使用において大きな問題です: 上記のマージソートの実装がとても長いリスト (例えば1,000,000以上の要素を含む) のソートに対して呼び出されたら、スタックオーバーフローが引き起こされることは疑う余地がありません。 後の章で、ATS の線形型を使って merge 関数の末尾再帰的実装を紹介します。
この章のコード全体と追加のテストコードは オンライン から入手できます。