マージソートのイメージ！！

Merge_sort

分割統治法の一例。

概要

マージソートは、配列を半分に分割し、それぞれを再帰的にソートしてから、2 つのソートされた配列をマージすることで全体をソートするアルゴリズムである。

手順

配列の要素数が 1 つになるまで、分割していく。
（実際には、左の index と右の index が同じになるまで）
（もっと具体的には、index を半分にしながら、再帰をねずみ算回していく。）
その後、分割された配列を隣の配列とマージしていく。

Merge の仕方

2 つのグラフをまるで剣道の団体戦かのように比較していく。

🥋 剣道の勝ち抜き戦のイメージ ⚔️

実際の対戦風景（配列でシミュレーション）

🧩 配列マージの具体例

凡例：

• 下線: 現在対戦中の選手 ⚔️
• ✓: すでに勝負が決まった選手 🏆

💡 マージソートの核心ポイント

1. 🎯 最小限の比較
   「常に先鋒同士で一本勝負」→ 比較回数は必要最小限！

2. 🔒 順序保証
   勝者は即ベンチ入りで順序が守られる → 安定的な並び替え

3. 🛡️ 安定ソート
   一度勝った剣士（数字）は、より強い相手とは再戦しない

4. 🔄 効率的な統合
   片方のチームが全滅したら、残りのメンバーは自動的に結果配列へ入隊

具体的には、

1. 左側の配列の先頭と右側の配列の先頭を比較する。
2. 小さい方を仮の配列に追加する。
3. 追加した方の配列のインデックスを進める。
4. 1〜３を繰り返す。
5. どちらかの配列が空になったら、残りの配列をそのまま新しい配列に追加する。

💻 コード実装イメージ

// 初期設定
int left[] = {1, 3, 4, 5};
int right[] = {2, 6, 7, 8};
int tmp[8] = {0};
int l_idx = 0, r_idx = 0, t_idx = 0;

// 第1試合: left[0] vs right[0] → 1 < 2
tmp[t_idx++] = left[l_idx++];  // tmp = {1, _, _, _, _, _, _, _}

// 第2試合: left[1] vs right[0] → 3 > 2
tmp[t_idx++] = right[r_idx++]; // tmp = {1, 2, _, _, _, _, _, _}

// 第3試合: left[1] vs right[1] → 3 < 6
tmp[t_idx++] = left[l_idx++];  // tmp = {1, 2, 3, _, _, _, _, _}

// 第4試合: left[2] vs right[1] → 4 < 6
tmp[t_idx++] = left[l_idx++];  // tmp = {1, 2, 3, 4, _, _, _, _}

// 第5試合: left[3] vs right[1] → 5 < 6
tmp[t_idx++] = left[l_idx++];  // tmp = {1, 2, 3, 4, 5, _, _, _}

// 残りの選手を自動入隊
while (r_idx < 4)
    tmp[t_idx++] = right[r_idx++]; // tmp = {1, 2, 3, 4, 5, 6, 7, 8}

実装

void Merge_sort(int arr[], int tmp[], int left, int right)
{
	int mid;
	if (left >= right)
		return;
	mid = (left + right) / 2;
	/* 再帰の構造を利用して、ねずみ算的に分割していく。 */
	Merge_sort(arr, tmp,  left, mid); /* 分割：左側 */
	Merge_sort(arr, tmp,  mid + 1, right); /* 分割：右側 */
	/* ここで、分割された配列をマージしていく。 */
	Merge(arr, tmp, left, mid, right); /* 合体！ */
}

/* 革新部分！！ */
void Merge(int arr[], int tmp[], int left, int mid, int right)
{
	int l_idx = left;  // 左側のインデックス
	int r_idx = mid + 1; // 右側のインデックス
	int t_idx = left;   // 仮の配列のインデックス

	// 左右の配列を比較しながらマージ
	while (l_idx <= mid && r_idx <= right)
	{
		if (arr[l_idx] <= arr[r_idx])
			tmp[t_idx++] = arr[l_idx++];
		else
			tmp[t_idx++] = arr[r_idx++];
	}
	// 左側の残りを追加
	while (l_idx <= mid)
		tmp[t_idx++] = arr[l_idx++];

	// 右側の残りを追加
	while (r_idx <= right)
		tmp[t_idx++] = arr[r_idx++];

	// 元の配列に戻す
	while (left <= right )
	{
		arr[left] = tmp[left];
		left++;
	}
}

特徴

• 最悪時時間計算量: O(n log n)
• 平均時時間計算量: O(n log n)
• 最良時時間計算量: O(n log n)（すでにソートされている場合も同様）
• 空間計算量: O(n)（追加の配列が必要）
  (空間計算量とはそのアルゴリズムが使用する追加のメモリ量を指す。)
• 安定ソート: 同じ値の要素の順序が保持される。