java - 通常のソートされたリストよりも逆ソートされたリストをソートするとマージソートが速いのはなぜですか?

Question

昇順で出力するマージソートアルゴリズムの比較ベースの分析を行っています。昇順でソートされたリストの代わりに逆にソートされたリストを指定すると、より高速である (比較が少ない) ことに気付きました。誰も理由を説明できますか？

Answer 1

長さ M と N の 2 つのリストをマージするには、最大でも M+N-1 回の比較が必要です。最初のリストのすべてのエントリが 2 番目のリストのエントリよりも小さい場合、必要な比較は M 回だけです。2 番目のリストのすべてのエントリが最初のリストのエントリよりも小さい場合、必要な比較は N 回だけです。

ソートする数値の合計が 2 の効力でない場合、異なる長さの 2 つのリストに分割する場合があります。これら2つのうち最初の要素が1つ多い方法でマージソートを実装したと思われます。つまり、そのパーティションとマージでは M = N+1 です。要素の順序が逆の場合、2 番目のリストのすべての要素は最初のリストの要素よりも小さくなり、正しい順序の場合は M ではなく N の比較が必要になります。

並べ替えたいリストの効力が 2 の場合、通常の順序と逆の順序に違いはありません。

Answer 2

ソートコードにエラーがあるはずです。

私の理解では、リテラルのマージソートによって実行される比較の数は、データとは無関係である必要があります。つまり、それより悪くなることはありませんがO(n log n)、良くなることもありません（「自然なマージソート」やTimSortなどのスマートな変更を行わない限り）。