マージソートの 1 つの方法が他の方法よりも高速であるべきだという議論を見つけることができませんでした。
ボトムアップとトップダウンのマージソート、およびその他のバリアントは、90 年代によく研究されてきました。簡単に言えば、個々のキーの比較回数としてコストを測定すると、最良のコストは同じ (~ (n lg n)/2)、トップダウンの最悪のコストは最悪のコスト以下です。ボトムアップのケース (ただし ~ n lg n の両方) およびトップダウンの平均コストは、ボトムアップの平均ケース (ただし両方 ~ n lg n) 以下です。ここで、「lg n」はバイナリ対数。違いは線形項に由来します。もちろん、n=2^p の場合、2 つのバリアントは実際にはまったく同じです。つまり、比較に関しては、トップダウンは常にボトムアップよりも優れています。さらに、トップダウン マージ ソートの「半々」分割戦略が最適であることが証明されています。研究論文は、Flajolet、Golin、Panny、
以下は、Erlang で書かれた著書Design and Analysis of Purely Functional Programs (College Publications、英国) で思いついたことです。
tms([X|T=[_|U]]) -> cutr([X],T,U);
tms(T) -> T.
cutr(S,[Y|T],[_,_|U]) -> cutr([Y|S],T,U);
cutr(S, T, U) -> mrg(tms(S),tms(T)).
mrg( [], T) -> T;
mrg( S, []) -> S;
mrg(S=[X|_],[Y|T]) when X > Y -> [Y|mrg(S,T)];
mrg( [X|S], T) -> [X|mrg(S,T)].
これは安定ソートではないことに注意してください。また、Erlang (および OCaml) では、メモリを節約したい場合、パターンでエイリアス(ALIAS=...) を使用する必要があります。ここでの秘訣は、リストの長さを知らずにリストの真ん中を見つけることです。これは、入力リストへの 2 つのポインターを処理する cutr/3 によって行われます。1 つは 1 ずつインクリメントされ、もう 1 つは 2 ずつインクリメントされます。したがって、2 番目が最後に到達すると、最初の 1 つは中間になります。(これは Olivier Danvy の論文から学びました。) この方法では、長さを追跡する必要がなく、リストの後半のセルを複製しないので、(1/2 )n lg n 余分なスペース、対 n lg n。これはあまり知られていません。
関数型言語や連結リスト (Knuth、Panny、Prodinger) にはボトムアップのバリアントが望ましいとよく言われますが、これは真実ではないと思います。
私はあなたと同じように、マージソートに関する議論が不足していることに困惑していたので、独自の調査を行い、それについて大きな章を書きました。現在、マージソートに関する資料を追加した新版を準備中です。
ところで、キュー マージ ソートやオンライン マージ ソートなど、他にもバリエーションがあります (後者については私の著書で説明しています)。
[編集: コストの尺度は比較の数であるため、配列とリンク リストの選択に違いはありません。もちろん、リンクされたリストを使用してトップダウンのバリアントを実装する場合は、キーの数を必ずしも知っているとは限らないため、賢くする必要がありますが、毎回少なくとも半分のキーをトラバースする必要があります。合計で (1/2)n lg n セルを再割り当てします (賢い場合)。リンクされたリストを使用したボトムアップ マージ ソートは、実際には追加のメモリ (n lg n + n セル) を必要とします。したがって、リンクされたリストであっても、トップダウンのバリアントが最良の選択です。プログラムの長さに関しては、マイレージはさまざまですが、関数型言語では、安定性が必要ない場合は、トップダウン マージ ソートをボトムアップ マージ ソートよりも短くすることができます。マージソートの実装の問題を議論する論文がいくつかあります。Katajinen と Larsson Traff (1997 年) によるMergesort プログラムの綿密な分析]