ここでは 挿入ソート（Insertion Sort） と マージソート（Merge Sort） を、プログラミング初心者でもイメージしやすいように 図解（ASCIIアート） で分かりやすく解説します。
挿入ソート（Insertion Sort）の図解
挿入ソートとは？
- 手持ちのトランプを並べる時の動きと同じ
- 左側は「すでに並んでいる」領域
- 右側のカードを左の正しい位置に挿入していく
図解（イメージしやすいステップ）
対象配列：
[5, 2, 4, 6, 1, 3]
ステップ 1：2 を並んでいる部分（5）に挿入
5 | 2 4 6 1 3
↑
並んでいる部分は 5 だけ
2 を正しい位置へ移動 → 5 と入れ替え
結果：
[2, 5, 4, 6, 1, 3]
ステップ 2：4 を [2,5] の中に挿入
2 5 | 4 6 1 3
↑
挿入する値 4
5 の前に入る（2 の後）
結果：
[2, 4, 5, 6, 1, 3]
ステップ 3：6 → すでに正しい場所
2 4 5 | 6 1 3
↑
6 は正しいのでそのまま
ステップ 4：1 を正しい場所に挿入
2 4 5 6 | 1 3
↑
右端の 1 を左へ移動し続ける：
6 > 1 → 移動
5 > 1 →
4 > 1 →
2 > 1 →
結果：
[1, 2, 4, 5, 6, 3]
ステップ 5：3 を挿入
1 2 4 5 6 | 3
↑
6 > 3
5 > 3
4 > 3
2 < 3 ← 挿入位置
結果：
[1, 2, 3, 4, 5, 6]
挿入ソートの特徴まとめ（初心者向け）
- 小さな配列に強い
- ほぼ整列済みのデータには非常に高速
- 比較的実装がシンプル
- 計算量：
- 最悪：O(n²)
- 最良（ほぼ整列）：O(n)
マージソート（Merge Sort）の図解
マージソートとは？
- 分割して → ソートして → 結合する
- Divide（分割） → Conquer（解く） → Merge（マージ）
図解（大きな流れ）
配列：
[5, 2, 4, 6, 1, 3]
① ひたすら2つに分割していく
[5 2 4 6 1 3]
↓分割
[5 2 4] [6 1 3]
[5 2 4] → [5 2] と [4]
[5 2] → [5] と [2]
[6 1 3] → [6 1] と [3]
[6 1] → [6] と [1]
最終的に全部バラバラに：
[5] [2] [4] [6] [1] [3]
② 2つずつマージしながら整列（ここがキモ）
マージ例： [5] と [2]
5 と 2 を比較 → 小さい順に並べる
→ [2, 5]
[6] と [1]
→ [1, 6]
③ マージしていく様子（図）
[5] [2] [4] [6] [1] [3]
↓マージ
[2 5] [4] [1 6] [3]
↓マージ
[2 4 5] [1 3 6]
↓マージ（最後）
[1 2 3 4 5 6]
マージソートの特徴まとめ（初心者向け）
- 計算量は 常に O(n log n)（かならず速い）
- 大きな配列に強い
- 安定ソート
- 分割と結合の仕組みがやや難しめ（図で理解すると簡単）
要点を比較すると…
| ソート | 得意 | 苦手 | 計算量 | 特徴 |
|---|---|---|---|---|
| 挿入ソート | 小配列、ほぼ整列済み | 大きい配列 | 最悪 O(n²) | 実装が簡単・直感的 |
| マージソート | 大規模データ全般 | 追加メモリが必要 | 常に O(n log n) | 分割→結合で確実に速い |