ソート済みリンクリストの merge

2 台のサーバーが、それぞれ時刻順にログを吐いています。どちらの中身もきれいに並んでいます。この 2 本を、時刻順のまま 1 本にまとめたい、という話です。

残り全部から一番古いものを探すのは、もったいない

素直にやるなら、まだ取っていないログを全部見比べて一番古いものを選ぶ、を繰り返すことになります。1 件選ぶたびに残り全部を見るので、件数が増えると急に重くなります。

けれど、両方すでに時刻順です。ということは、まだ取っていない中で一番古いログは、必ずどちらかの先頭にあります。奥のほうを見る意味はありません。見比べるのは、いつでも 2 件だけで足ります。

先頭 2 件を比べて、取ったほうだけ進める

それぞれのログに、どこまで読んだかを覚えておく位置を 1 つずつ持たせます。

JavaScript でも同じです。

取ったほうの位置だけを進めるのが要です。両方進めてしまうと、選ばれなかった側の 1 件が誰にも見られないまま置き去りになります。

[1, 3, 5] と [2, 4, 6] を並べたときの動きは次のとおりです。

同じ時刻が両方にあったとき、<= なら logA の側が先に出ます。< にすると逆になります。どちらでも並びは時刻順ですが、同着の扱いが変わるので、比較の向きは意識して決めてください。

片方が先に尽きる

表の最終行で logA の側が末尾を越えました。ここで比較を続けようとすると、存在しない場所を読むことになります。比べるのは「両方にまだ残っている間」だけです。

抜けたあとには、片方の残りがそのまま残っています。この残りは、すでに時刻順に並んでいて、しかも取り出し済みのどれよりも新しい。並べ替えは 1 回も要りません。そのままの順で後ろへ足せば終わりです。ここを忘れると結果が短くなり、しかも件数が合わないだけで並びは正しいので、原因に気づくまで時間がかかります。

片方が最初から空のときも、同じ理屈で片付きます。比較のループは 1 度も回らず、もう片方がまるごと残りとして出ていきます。特別扱いの分岐を書き足す必要はありません。

この「先頭 2 件だけ見る」は、分割して統合する並べ替えの後半そのものです。半分ずつに割ってそれぞれ並べ、最後にこの手順で 1 本へ戻します。全体が速く終わるのは、統合の 1 回が全件を 1 度なぞるだけで済むからです。

札でつないだリストが相手なら、新しい入れ物すら要りません。取ると決めたノードの札を、結果の末尾から張り替えていくだけです。値のコピーが 1 回も起きないので、1 件あたりが大きいデータほど差が出ます。

1. 両方の配列は昇順ソート済みであると仮定して良い
2. 2 ポインタ法で O(n + m) で実装すること
3. 戻り値は昇順ソートされた新しい配列