《アルゴリズムを学ぶ》22.マージソート

# Overview
マージソート（Merge Sort） は、N個の数$A_1, A_2, A_3, ..., A_N$を計算量$O(log N)$で小さい順に整列できる。大規模なデータにも適しており、かつ安定ソートであり、比較ソートの中でもシンプルかつ強力なアルゴリズムである。
[1.マージソートの基本概念](#1-マージソートの基本概念)
[2.マージソートのアルゴリズム](#2-マージソートのアルゴリズム)
[3.マージソートの応用](#3-マージソートの応用)
[4.典型問題を解いてみる](#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) アルゴリズム
1. 空の列Sを用意する
1. 配列を中央で 2 つに分割
1. それぞれを再帰的にマージソートで整列
1. 2 つのリストの先頭を比較し、小さい方を新しいリストに追加
1. すべての要素がマージされるまで繰り返す

例:
列[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) マージソートの実装
**基本的なマージソート**
```python
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) に近づく）
```python
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番目に小さい値を求める問題に応用できる
```python
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 個の整数をマージソートでソートせよ。**
> [参考： ABC315 B - Merge Sort](https://atcoder.jp/contests/abc315/tasks/abc315_b)
<details><summary> 回答　</summary>

```python
N = int(input())
arr = list(map(int, input().split()))

sorted_arr = merge_sort(arr) # 「基本的なマージソート」の記載は省略する
print(*sorted_arr)
```
</details>

### 例題2. K 番目に小さい要素を求める
**問題: N 個の整数 A から K 番目に小さい値を求めよ。**
> [参考： ABC318 B - Kth Smallest Element](https://atcoder.jp/contests/abc318/tasks/abc318_b)
<details><summary> 回答　</summary>

```python
N, K = map(int, input().split())
A = list(map(int, input().split()))

sorted_A = merge_sort(A) # 「基本的なマージソート」の記載は省略する
print(sorted_A[K - 1])
```
</details>

### 例題3. 数列の反転数を求める
**問題: N 個の整数の 転倒数（逆順ペアの数） を求めよ。**
> [参考： ABC319 C - Inversion Count](https://atcoder.jp/contests/abc319/tasks/abc319_c)
<details><summary> 回答　</summary>

```python
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)
```
</details>