Rubyでマージソート

bunoacts.hatenablog.com

クイックソートは、元データの並び方が悪いと、ソートの効率がバブルソートと大差がなくなってしまう（最悪時間計算量が O(n²)）

こんな場合、より効率的にソートできるアルゴリズムがマージソートである。

マージソートの流れを簡単に説明すると、

全体を小さなブロックに区切る
1. 全体を2つに分ける
2. 分けた2つを、さらにそれぞれ2つに分ける
3. ブロックの大きさが1になるまで分け続ける
各ブロック同士をソートしながらつなぎ合わせる（マージ）
全体がソート済みになったら完了

f:id:bunoacts:20160527114339g:plain

WikipediaにRubyの実装例があるので、コメント追記しながら処理を追ってみる。

def mergesort lst
    _mergesort_ lst.dup  # 副作用で配列が壊れるので、複製を渡す
end

def _mergesort_ lst
    return lst if (len = lst.size) <= 1

    # pop メソッドの返す値と副作用の両方を利用して、lst を二分する
    lst2 = lst.pop(len >> 1)

    _merge_(_mergesort_(lst), _mergesort_(lst2))
end

# 二つの配列をソートしてつなぎ合わせる（マージ）
def _merge_ lst1, lst2
    len1, len2 = lst1.size, lst2.size
    result = Array.new(len1 + len2)
    a, b = lst1[0], lst2[0]
    # i: マージ後の配列resultのインデックス
    # j: lst1のインデックス
    # k: lst2のインデックス
    i, j, k = 0, 0, 0
    loop {
        if a <= b
            result[i] = a
            i += 1 ; j += 1
            break unless j < len1
            a = lst1[j]
        else
            result[i] = b
            i += 1 ; k += 1
            break unless k < len2
            b = lst2[k]
        end
    }
    while j < len1 do
        result[i] = lst1[j]
        i += 1 ; j += 1
    end
    while k < len2 do
        result[i] = lst2[k]
        i += 1 ; k += 1
    end
    result
end

実行例

[2] pry(main)> ary = ('a'..'z').to_a.shuffle
=> ["h", "w", "y", "j", "c", "f", "g", "o", "p", "b", "q", "s", "e", "d", "a", "i", "z", "k", "n", "v", "x", "m", "u", "r", "l", "t"]
[3] pry(main)> mergesort(ary)
=> ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]