Overview
マージソート（Merge Sort） は、N個の数$A_1, A_2, A_3, ..., A_N$を計算量$O(log N)$で小さい順に整列できる。大規模なデータにも適しており、かつ安定ソートであり、比較ソートの中でもシンプルかつ強力なアルゴリズムである。
1.マージソートの基本概念
2.マージソートのアルゴリズム
3.マージソートの応用
4.典型問題を解いてみる
1. マージソートの基本概念
マージソートは、以下の 2 つのステップで構成される：
- 配列を半分に分割し、再帰的にマージソートを適用
- 分割された 2 つの配列をマージ（結合）する
(1) 分割統治法とは？
- 「大きな問題を小さな問題に分割し、それらを解いて最終的に結合する」
- マージソートでは、配列を再帰的に分割し、最後に統合（マージ）する
- 典型的な O(N log N) のアルゴリズム
マージソートのポイント
- 計算量：O(N log N)（分割 O(log N) × マージ O(N)）
- 安定ソート（同じ値の要素の順序が保持される）
- 追加のメモリ O(N) が必要（配列をコピーするため）
- データの順番に依存しない（最悪 O(N log N) を保証）
2. マージソートのアルゴリズム
(1) アルゴリズム
- 空の列Sを用意する
- 配列を中央で 2 つに分割
- それぞれを再帰的にマージソートで整列
- 2 つのリストの先頭を比較し、小さい方を新しいリストに追加
- すべての要素がマージされるまで繰り返す
例:
列[13, 75, 34, 50, 20, 28, 62, 11]
↓（1の操作後）
列A[13, 75, 34, 50] 列B[20, 28, 62, 11]
↓（2の操作後）
列A[13, 34, 50, 75] 列B[11, 20, 28, 62]
↓（３の操作でAの先頭13とBの先頭11を比較。小さい方の値11を列Sに移す）
列A[13, 34, 50, 75] 列B[20, 28, 62] 列S[11]
↓（４を満たすまで３の操作を繰り返す）
列A[34, 50, 75] 列B[20, 28, 62] 列S[11, 13]
↓（繰り返し）
列A[34, 50, 75] 列B[28, 62] 列S[11, 13, 20]
↓（繰り返し）
列A[34, 50, 75] 列B[62] 列S[11, 13, 20, 28]
↓（繰り返し）
列A[50, 75] 列B[62] 列S[11, 13, 20, 28, 34]
↓（繰り返し）
列A[75] 列B[62] 列S[11, 13, 20, 28, 34, 50]
↓（繰り返し）
列A[75] 列B[] 列S[11, 13, 20, 28, 34, 50, 62]
↓
列A[] 列B[] 列S[11, 13, 20, 28, 34, 50, 62, 75]
処理終了
(2) マージソートの実装
基本的なマージソート
def merge_sort(arr):
if len(arr) <= 1: # 配列が 1 要素ならそのまま返す（再帰の終了条件）
return arr
mid = len(arr) // 2 # 配列を半分に分割
left_half = merge_sort(arr[:mid]) # 左側をソート
right_half = merge_sort(arr[mid:]) # 右側をソート
return merge(left_half, right_half) # マージして返す
def merge(left, right):
sorted_arr = []
i = j = 0
# 2つのリストをマージ
while i < len(left) and j < len(right):
if left[i] <= right[j]:
sorted_arr.append(left[i])
i += 1
else:
sorted_arr.append(right[j])
j += 1
# 残った要素を追加
sorted_arr.extend(left[i:])
sorted_arr.extend(right[j:])
return sorted_arr
# 使用例
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr) # [3, 9, 10, 27, 38, 43, 82]
- 計算量: O(N log N)
- メモリ使用量: O(N)（新しい配列を作るため）
3. マージソートの応用
(1) インプレース（メモリを追加せず）でのマージ
メモリ使用量を抑えられる（O(1) に近づく）
def merge_inplace(arr, left, mid, right):
temp = arr[left:right+1]
i = left
j = mid + 1
k = left
while i <= mid and j <= right:
if temp[i - left] <= temp[j - left]:
arr[k] = temp[i - left]
i += 1
else:
arr[k] = temp[j - left]
j += 1
k += 1
while i <= mid:
arr[k] = temp[i - left]
i += 1
k += 1
(2) K番目に小さい要素を求める
K番目に小さい値を求める問題に応用できる
def kth_smallest(arr, k):
sorted_arr = merge_sort(arr)
return sorted_arr[k - 1]
print(kth_smallest([3, 2, 1, 5, 4], 3)) # 3番目に小さい値 → 3
4. 典型問題を解いてみる
例題1. マージソートの実装
問題: N 個の整数をマージソートでソートせよ。
回答
N = int(input())
arr = list(map(int, input().split()))
sorted_arr = merge_sort(arr) # 「基本的なマージソート」の記載は省略する
print(*sorted_arr)
例題2. K 番目に小さい要素を求める
問題: N 個の整数 A から K 番目に小さい値を求めよ。
回答
N, K = map(int, input().split())
A = list(map(int, input().split()))
sorted_A = merge_sort(A) # 「基本的なマージソート」の記載は省略する
print(sorted_A[K - 1])
例題3. 数列の反転数を求める
問題: N 個の整数の 転倒数（逆順ペアの数） を求めよ。
回答
def merge_count(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, left_inv = merge_count(arr[:mid])
right, right_inv = merge_count(arr[mid:])
merged, merge_inv = merge_and_count(left, right)
return merged, left_inv + right_inv + merge_inv
def merge_and_count(left, right):
sorted_arr = []
i = j = inv_count = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
sorted_arr.append(left[i])
i += 1
else:
sorted_arr.append(right[j])
j += 1
inv_count += len(left) - i
sorted_arr.extend(left[i:])
sorted_arr.extend(right[j:])
return sorted_arr, inv_count
N = int(input())
arr = list(map(int, input().split()))
_, inv_count = merge_count(arr)
print(inv_count)