algorithm - マージソートが最大で 6 n log n の配列アクセスを行うのはなぜですか?

Question

私はコーセラ プリンストン アルゴリズムのマージ ソートに関する講義を見ています。マージが最大 6 n log n 配列アクセスであることを除いて、すべての分析を理解しています。

なぜ6？

Answer 1

6 つの配列アクセスを取得するには、やや非効率的なマージ プロセス:

read  - read an element from even run for compare
read  - read an element from odd  run for compare
      - compare
read  - read the lower element again for copy
write - write the lower element to the output array for copy
...   - after merge copy back
read  - read element from output array to copy back
write - write element back to original array to copy back

通常のケースでは、移動する要素ごとに 1 回の読み取りと 1 回の書き込みが行われますが、要素が大きすぎて文字列などの変数に収まらない場合を考えてみてください。したがって、比較後、移動する文字列を再度読み取る必要があります。

通常、マージソートのコーディング方法によっては、コピーバック操作を回避できます。

Answer 2

Tim Roughgarden の分析 (ビデオ '1 - 7 - Merge Sort- Analysis (9 min.mp4')) を見たところ、彼も 6 と言っています。それぞれの説明は手を振っているように感じますが、あまりにも単純なため、説明が必要であることに気付いていないのかもしれません。

補助配列にコピーするときに、n (または k) ごとに配列に 2 回アクセスします。 aux[k] = a[k]; 次に、最悪の場合、サブ配列 (定数を比較するだけの場合) を使い果たすことはなく、さらに 4 つの配列アクセスがあります else if (less(aux[j], aux[i])) a[k] = aux[j++];(たとえば、入力が逆の順序である場合)、または各比較が失敗し、比較の後に else が開始される場合 (正しい順序)、または 2 つの組み合わせ。それは問題ではありません。最悪の場合の定義により、定数を介した配列アクセスを ( if (i > mid)orを使用してelse (j > hi)) エスケープできないため、k ごとにさらに 4 つあるということだけです。合計は 6 です。

(コードの各行は Sedgewick のテキストの p271 ページです。)