[解決済み] ヒープソートとマージソートの速度比較 [重複]について

質問

大きな配列を繰り返し処理する場合、ヒープソートとマージソートではどちらのアルゴリズムが速いでしょうか？なぜどちらかのアルゴリズムが速いのですか？

どのように解決するのですか？

時間の複雑さは同じですが、定数係数は違います。一般に、マージソートは2つのランから順次読み込み、マージされた1つのランに順次書き込むので、4ウェイ以上のキャッシュを持つ典型的なシステムでは、マージソートは著しく速くなります。私は、Cで書かれたマージソートが、アセンブリで書かれた最適化されたヒープソートよりも高速であったことを記憶しています。

ヒープソートはデータをスワップするので、1回のスワップで2回の読み込みと書き込みが発生しますが、マージソートはデータを移動するので、1回の移動で1回の読み込みと書き込みが発生するという問題点があります。

マージソートの主な欠点は、元の配列と同じサイズ（またはオプションで元の配列の 1/2 サイズ）の 2 番目の配列（またはベクトル）がワーキングストレージとして必要になることですが、4GB 以上の RAM を搭載した PC では、通常これは問題ではありません。

私のシステムでは、Intel 3770K 3.5 ghz、Windows 7 Pro 64 bit、Visual Studio 2015で、2^24 = 16,777,216 64 bit 符号なし整数をソートするには、ヒープソートが7.98秒かかるのに対し、ボトムアップマージソートは1.59秒、トップダウンマージソートは1.65秒で完了します。