私は 2 通りのマージ ソート アルゴリズムを調べていて、マージ パスを減らすことで時間の点でより良い利益を得ることができるかどうかを考えていました。
たとえば、双方向のマージでは、次の繰り返しがあります。
T(n) = 2T(n/2) + O(n)
これは N.log-base2(N) の時間複雑度を持っています
問題を 4 で割り、4 つのサブ配列をマージすると、次のようになります。
T(n) = 4T(n/4) + O(n)
これは N.log-base4(N) の時間計算量を持つ必要があります
マージ パスの数が減ったため、マージ ソートを実装するときにこれを考慮する必要がありますか?
たとえば、64 要素の配列の場合、最初のアプローチでは 6 つのパスがあり、2 番目のアプローチでは 3 つのパスがあります。
編集：
さて、2T(n/2) ではパスごとに N 回の比較を行い、4T(n/4) ではパスごとに 3*N 回の比較を行うことになりますか? 要素を結果配列に移動するコストについてはどうですか?それは各パスで同じままですか?
数値の底 4 の対数は、数値の底 2 の対数のちょうど半分であることに注意してください。したがって、定数係数の高速化のみを導入しています。そうでない場合を除いて、実際のマージのコストに同様の定数係数 SLOWDOWN を導入するためです (2 方向マージでは項目ごとに 1 つの比較が必要であり、4 方向マージでは最大 3 が必要になる場合があります)。そのため、パスが少なくても、パスごとにコストが高くなります。そのため、コードをかなり複雑にしましたが、その利点は疑問視されています。
理にかなっているように聞こえますが、そうではありません。この場合、4 つの要素をそれぞれ並べ替えるには、少なくとも 5 回の比較を行う必要があるからです。このようにして、5*N*log4(N) の比較があり、これは N*log2(N) よりも 5*log(2)/log(4) 倍大きくなります。
分解木の高さは log 4 n ですが、実行時間は n log 4 n ではありません。
最初のステップでは、サイズ n/4 の 4 つのリストがあり、それらのマージには n/4 + n/4 + n/2 の比較が必要です。ただし、通常は n/2 の比較が必要なため、ツリーの高さを半分にしますが、各マージを 2 で乗算するため、合計実行時間は 2 分割よりも良くありません。（ツリーの他の深さについては、2 つのブランチを持つツリーと比較して、少なくとも 2 回の比較が必要であることを証明できます）。
PS:実行時間とは、比較の数を意味します。