クイックソートではなくマージソートで順番に並べ替えが効率的な配列

Question

クイックソートではなくマージソートを使用して、その内容を順番に並べ替えた方がよいでしょうか？

Answer 1

マージソートではより多くの動きがありますが、クイックソートよりも比較回数は少なくなります。文字列へのポインタの配列をソートする場合、文字列が比較されている間はポインタだけが移動されます。この種の状況では、マージソートが高速です。

整数の配列をソートする場合、ソートの計算/基数は最も速くなります。マージソートと整数配列のクイックソートについては、16個のレジスタ（実行ポインタへのポインタのうちの8個が使用されています）を持つプロセッサで実行すると、4ウェイマージソートは通常quicksortよりも少し速くなります。 4ウェイマージソートでは、1.5 xの比較、0.5 xの移動が行われるため、操作の総数は同じですが、比較の方がキャッシュの利便性が向上し、4ウェイの場合は2倍よりも約15％方法。