BUILD YOUR UNDERSTANDING
情報処理技術者試験の用語集
言葉の意味を確かめて、問題への理解を一歩深めましょう。
マージソート
分けてから順序を保って併合する
マージソートは、データを部分に分け、それぞれを整列し、整列済みの列を併合して全体を整列する方法です。マージは併合を意味します。二つに分ける方式では、要素が一つになるまで分割し、戻りながらまとめる考え方が基本です。クイックソートと同じ分割統治法でも、分割と統合の役割が異なります。
併合の手順
整列済みの列Aが1、4、8、列Bが2、3、9なら、それぞれの先頭を比較します。小さい方を結果へ移し、その列の次の要素を比較に使います。一方が空になったら、もう一方の残りを順に加えます。既に各列の順序がそろっているため、毎回全要素の最小値を探し直す必要はありません。
Pythonによる併合例
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
return result + left[i:] + right[j:]
等しい値では左側を先に選ぶことで、元の順序を保つ構成にできます。
計算量と領域
二分割する標準的な方法では段数が対数的になり、各段で合計n個程度を併合するため、時間計算量はO(n log n)です。配列を使う一般的な実装では補助領域が必要になります。連結リストで参照をつなぎ直す方式などでは、領域の扱いが異なるため、実装の前提を確認します。
利用場面と試験
安定性が必要な整列や、記憶装置上の大きなデータを部分ごとに処理する外部整列で、併合の考え方が役立ちます。試験では、分割した直後と併合後の配列を区別します。整列済みの二列の併合は全体のソートより単純な操作です。クイックソートのピボットによる分割と、マージソートの整列済み部分を合わせる処理を対比すると、アルゴリズムの流れを見分けやすくなります。
参考資料
内容確認日:2026-11-13