マージソートで配列を5倍に分けることができないのはなぜですか？マージソートでは

Question

であり、常に2倍に割ります。なぜ私たちは2回以上それを分割しないのですか？ヒープソートとマージソートの間でより良いですか？I

Answer 1

なぜそれを試してみてください。 2ではなく5つに分割するマージソートを作成し、そのパフォーマンスをテストします。学習する最善の方法は試してみることです。

これは計算上の複雑さには影響しないため、改善は最大でも一定の要素です。マージパスの数をlg（5）≈2.3で減らすことができますが、マージステップでは優先キューが必要になります。これは、2フェーズマージで使用される単一比較よりも2.3倍以上遅くなります。

2つ以上に分割することはpolyphase merge sortとして知られており、マージパスの回数を最小限に抑える必要がある場合に使用されます。