マージソート変形版オーダー考察

マージソートがO(log(N))のアルゴリズムであることはよく知られているが、これは配列を再帰的に二分してマージすることでこのオーダーは得られる。
今回はこの「1つの配列のソート」ではなく「n個の配列のソート」を考えたい。

問題

配列V[1]…V[n] (それぞれ長さはL[1]…L[n])が与えられているとする。この時これらをマージする際に必要なコストを求めよ。ただし、

• 任意の値の比較に要するコストはc (定数時間)とみなせる

以下では最悪計算量を考えていくことにする。

簡単化した問題を解く

まずは2つで考えることにする。配列 N, M があり、これらをマージする。 N, M はソート済みとする。任意のステップは次のように場合分けされる。以下 n, m はそれぞれ N, M の先頭要素とする。

• S(N) = S(M) = 0 の場合終了
• S(N) = 0 の場合 M からひとつ取り (N, M-1) に対して再帰
• S(M) = 0 の場合 N からひとつ取り (N-1, M) に対して再帰
• head N < head M の場合 N から一つ取り (N-1, M) に対して再帰
• head N >= head M の場合 M から一つ取り (N, M-1) に対して再帰

これから、

• N, M 何れかの大きさが 0 になると比較は起きない
• 全体のサイズは各ステップで1減少する

ことが言える。N, Mをすべてなくすためのステップ数はN + Mで与えられるので、最悪計算量は

O(N+M)

で与えられる。これで見る限りO(N)だし問題はなさそうだ。

元の問題をとく

同様に解く。最悪でも(L[1] + L[2] + … + L[n])だけ比較を行えば問題はない。今回比較にかかるコストはn個の要素中から最小値を求める問題なのでO(n)で求まることから計算量は

O(n(L[1] + L[2] + … + L[n]))

と求まる。Σ L[i]は全データ数にほかならないのでいいとして、nの係数はログ数が多くなるといけないことになる。最悪各レコードが別のファイルに書かれてあればO(N^2)。うやー。

対処法(誤)

なにが間違っていたかというと、V[1]…V[n]中の最小の要素を毎回O(n)で求めるのが無駄すぎるということ。毎回のステップでたかだか1つしか要素が変化しないわけで毎回最小の要素を求めるのはコストが大きすぎる。それを適切にキャッシュするためには次のように階層的なキャッシュを用意する必要がある。

             [0]
             / \
            /   \
           /     \
         [1]     [2]
         ..       ..
        /           \
  [2^(k-1)-1]     [2^k-2]
      / \           / \
     /   \        ..   \
    /     \             \
[2^k-1]  [2^k]      [2^(k+1)-2]
  / \     / \           / \
 /   \   /   \         /   \
[1] [2] [3] [4]  ..  [n-1] [n]

そうしておけばどの要素が更新されても、更新によるキャッシュの更新はlog(n)個にしか波及しない(以下略)

対処法(改)

上の二分木を見てなにか気づかないだろうか？――そう, ヒープ木そのものですね、ヒープ木で実装しようとしたくらいですからね。ってことは、標準ライブラリでサポートされている優先度キューを使うほうが楽です。

ただ、

正しいN個ソースのマージソートまとめ

1. N個のソースをpriority_queueに突っ込む
2. 以下をpriority_queueがなくなるまで続ける
   1. priority_queueの最小要素を拾ってくる
   2. 空ならskipして次へ
   3. 拾った要素を結果へ突っ込む
   4. 拾ったソースをpriority_queueに突っ込む