ソート済み 2 配列のマージ

つなげて並べ替えると、前提を捨てている

2 本の配列がどちらも昇順に並んでいるとき、まとめてから並べ替え直しても答えは出ます。ただしそれは O((n + m) log(n + m)) です。入力がすでに整っているという情報を、いったん捨ててから作り直していることになります。両方に 100 万個ずつ入っていれば、この捨て方の代償はそのまま待ち時間として返ってきます。

前提を使い切れば O(n + m) まで落とせます。落とし方の入口は「全体をどう並べるか」ではありません。

見るのは、2 本の先頭だけ

結果のいちばん前に来る値は、2 本の配列のどちらかの先頭にしかありません。ここが出発点です。片方から 1 個取り出すと、その配列の「いまの先頭」が 1 つ後ろへずれるだけで、状況はまったく同じ形に戻ります。

つまり毎回の判断は「どちらの先頭を取るか」の 1 つだけで、残り全体を見る必要はありません。先頭の位置は、配列そのものを削らずに、いま何番目を見ているかという数値で覚えておきます。

もう 1 つ決めておくことがあります。どちらかを読み切った瞬間から、比較は不要になります。残ったほうはすでに昇順で、しかも取り出し済みのどの値よりも大きいからです。

繰り返しを続ける条件を「両方に残っている間」にするか「どちらかに残っている間」にするかで、後始末の書き方が変わります。空の配列がそのまま渡ってきても壊れないのは、どちらの書き方でしょうか。

同じ値が来たとき、どちらを先に置くか

3 と 3 のように値が並んだ場合、どちらを先に置いても結果は昇順のままです。見た目では違いが出ません。

ただし、同じ値の要素どうしで元の並び順が保たれることを安定と呼びます。マージソートが安定ソートと呼ばれる根拠はここにあり、比較を < にするか <= にするかだけで、その性質は静かに壊れます。

静かに、というのが厄介なところです。整数だけを並べているうちは、どちらで書いても出力は同じなのでテストは通ります。壊れていることが見えるのは、値に別の情報がぶら下がっているときです。得点で並べた名簿を後から日付で並べ直すと、同点の人の順番が入れ替わる。そういう形で出てきます。今回の課題でも同値のときは a を先に置く指定があるので、比較記号を決め打ちする前に一度立ち止まってください。

やってみよう

mergeSorted(a, b) を実装してください。a と b はどちらも昇順ソート済みの整数配列です。sorted() や Array.prototype.sort は使わず、O(n + m) で 1 本にまとめます。同じ値のときは a 側を先に置いてください。空配列が渡ってくることもあります。

1. 関数 mergeSorted(a, b) を実装し、昇順にソートされた配列を返す
2. 双方向ポインタ を使い、計算量は O(n + m) であること (sorted() / Array.sort を使わない)
3. 同値の要素は a を先に置く 安定 なマージを行うこと