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

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

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

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

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

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

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

# 2 つの受付列で、いま先頭にいる人の番号を見比べる
head_x, head_y = queue_x[px], queue_y[py]
head_x <= head_y   # True なら x 側を先に呼ぶ

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

rest = queue_x[px:]   # 残りはこの順のまま使える

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

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

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

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

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

やってみよう

ひな形の TODO を完成させてください。先頭同士の比較と、選んだ側の位置更新を自分で書きます。入力を受け取る枠と説明つきの準備部分はそのまま使えます。

演習で使う書き方

本文の二つの受付列の合流と同じく、演習でも二つの先頭だけを比べます。append は結果の末尾への一要素追加です。片方が尽きた後の残りを付ける処理は用意し、両方が残っている間の比較・追加・位置更新を自分で書きます。

1. 先頭同士の比較と、選んだ側の位置更新を自分で実装する
2. 関数名と引数、入力と戻り値の形を保つ。説明つきの準備部分を使い、TODO の仮の処理を置き換える