ソート済み 2 配列のマージ
ソート済み 2 配列のマージ
このレッスンで分かること
マージ(merge) は、2 つのソート済み配列を 1 本のソート済み配列に結合する操作です- 素朴な発想は次の通りです
- これは動きますが、
O((n + m) log(n + m))かかります
ソート済み 2 配列のマージ とは
2 つの
ソート済み配列を 1 本のソート済み配列にマージする双方向ポインタの典型題を実装する。
マージ (merge) は、2 つのソート済み配列 を 1 本のソート済み配列に結合する操作です。マージソート の心臓部であり、外部ソート や データベース の merge join、タイムライン統合 などで使う基礎テクニックです。本レッスンでは O(n + m) でこれを実装し、双方向ポインタ の感覚を体に染み込ませます。
「ソート済みである」という前提が、なぜ計算量を
O(n log n)からO(n + m)に落とせるのかを意識して読み進めよう。
なぜ単純結合 + ソートではダメか
素朴な発想は次の通りです。
Python
def mergeSorted(a, b):
return sorted(a + b)これは動きますが、O((n + m) log(n + m)) かかります。a と b が既に ソート済み という情報を捨てているからです。一方、双方向ポインタを使えば O(n + m) で済みます。n = m = 10^6 のとき、ざっくり 20 倍近い差です。
双方向ポインタの考え方
a を指すポインタ i、b を指すポインタ j を用意し、a[i] と b[j] の小さい方を 結果配列 に積みます。積んだ側のポインタを 1 進める。これを i == len(a) または j == len(b) になるまで繰り返し、最後に残った片方の配列を後ろにまるごと連結すれば完成です。
図のポイント (テキスト併記)
- 各要素はちょうど 1 回ずつ
比較とpopを経るので、合計O(n + m)で確定します
各要素はちょうど 1 回ずつ 比較 と pop を経るので、合計 O(n + m) で確定します。
Python での実装
Python
def mergeSorted(a, b):
i, j = 0, 0
result = []
while i < len(a) and j < len(b):
if a[i] <= b[j]:
result.append(a[i])
i += 1
else:
result.append(b[j])
j += 1
result.extend(a[i:])
result.extend(b[j:])
return resultwhile のループ後に、残ったほうの配列を extend で追加します。a が先に尽きたなら b[j:] がそのまま残り、その逆もしかり、です。
JavaScript での実装
JavaScript
function mergeSorted(a, b) {
let i = 0, j = 0;
const result = [];
while (i < a.length && j < b.length) {
if (a[i] <= b[j]) result.push(a[i++]);
else result.push(b[j++]);
}
while (i < a.length) result.push(a[i++]);
while (j < b.length) result.push(b[j++]);
return result;
}while を 3 つに分割しても OK ですし、while (i < a.length || j < b.length) の中で a[i] ?? Infinity のようにしてもよいですが、上記のように 2 段書き のほうが読みやすいです。
安定性とタイブレーク
a[i] <= b[j]の<=を<にしてはいけない。タイブレークでaを優先しないと安定ソートの性質が崩れる。
マージは分割統治の典型例。マージソートのO(n log n)は、このmergeをlog n段繰り返すから得られる。
安定 (stable) というのは、同じキー の要素同士で元の 順序 が保たれることです。マージソート が 安定ソート と呼ばれるのは、まさにこの <= のおかげです。
よくある間違い
- 残った側の連結を忘れる。
whileを抜けた後、aかbのどちらかには必ず要素が残っている可能性がある。 <で比較してしまい、安定性が壊れる (テストには影響しないが、本番では事故になる)。- 結果配列を
aに上書きしてしまい、iのインデックスがずれる。必ず新しい配列を用意する。
やってみよう
mergeSorted(a, b) を実装してください。a, b はそれぞれ 昇順ソート済み の整数配列です。sorted() / Array.prototype.sort は使わず、双方向ポインタ で O(n + m) で書いてください。null や undefined は来ません。空配列が来てもよいように while の境界条件を意識しましょう。
よくある質問
Q. このトピックは実務でどう役立ちますか？
A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。
Q. 計算量はどう求めれば良いですか？
A. ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。
Q. 覚えるべき定番アルゴリズムは何ですか？
A. 二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。
次のレッスン
次は 配列の k 回転 で、配列を右へ k 回シフトする「回転 (rotate)」を、スライスと三段反転の 2 通りで実装する方法を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 2配列マージ の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 2配列マージ とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 関数
mergeSorted(a, b)を実装し、昇順にソートされた配列を返す 双方向ポインタを使い、計算量はO(n + m)であること (sorted()/Array.sortを使わない)- 同値の要素は
aを先に置く安定なマージを行うこと
入出力例
test-cases.txt
mergeSorted([1,3,5], [2,4,6]) → [1,2,3,4,5,6]
mergeSorted([1,2,3], [4,5]) → [1,2,3,4,5]
mergeSorted([1,2,2,5], [2,3,4]) → [1,2,2,2,3,4,5]
mergeSorted([1,2,3], [10,11,12]) → [1,2,3,10,11,12]
mergeSorted([5], [3]) → [3,5]
mergeSorted([1], [2,3,4,5,6]) → [1,2,3,4,5,6]