マージソート(Merge Sort)

マージソートは、分割統治法（divide and conquer）を用いた効率的なソートアルゴリズムです。以下にマージソートの特徴と仕組みを解説します。

1. マージソートの基本概念
2. マージソートのアルゴリズム
3. マージソートの実装例（JavaScript）
4. マージソートのシミュレーション
5. マージソートの特徴
6. マージソートの利点と欠点
1. 6.1. 利点
2. 6.2. 欠点
7. その他のソート

1. マージソートの基本概念

マージソートは以下の3つのステップで動作します：

分割（Divide）: 配列を半分に分割します
統治（Conquer）: 分割した各部分を再帰的にソートします
結合（Merge）: ソートされた部分配列を結合して完全にソートされた配列を作ります

もう少しわかりやすく整理すると次のようになります。

マージソートは大きく「分割（Divide）」と「統治・マージ（Conquer & Merge）」の2つのフェーズに分けられ、それぞれが再帰的に処理されます。

分割（Divide）フェーズ:
- 配列を単一要素（長さ1）になるまで再帰的に分割していきます
- これは「分割→分割→分割…」と木構造のように下へ下へと進みます
- 単一要素になった時点で、その要素は「すでにソート済み」とみなされます
統治・マージ（Conquer & Merge）フェーズ:
- 単一要素になった後、各部分配列をマージ（結合）していきます
- マージする際に、2つのソート済み配列を比較しながら新しいソート済み配列を作ります
- これを再帰呼び出しから戻りながら繰り返し、最終的に完全にソートされた1つの配列になります

2. マージソートのアルゴリズム

関数 マージソート(配列):
    もし 配列の長さ ≤ 1 なら:
        配列を返す（すでにソート済みとみなす）
    
    中間点 = 配列の長さ ÷ 2
    左側 = マージソート(配列の前半)
    右側 = マージソート(配列の後半)
    
    結合(左側, 右側)を返す

関数 結合(左側配列, 右側配列):
    結果配列 = 空の配列
    左側インデックス = 0
    右側インデックス = 0
    
    while 左側インデックス < 左側配列の長さ かつ 右側インデックス < 右側配列の長さ:
        if 左側配列[左側インデックス] <= 右側配列[右側インデックス]:
            結果配列に左側配列[左側インデックス]を追加
            左側インデックスを1増やす
        else:
            結果配列に右側配列[右側インデックス]を追加
            右側インデックスを1増やす
    
    残りの要素を結果配列に追加
    結果配列を返す

flowchart TD
    A[配列の入力] --> B{配列の長さ <= 1?}
    B -->|はい| C[そのまま返す
単一要素は既にソート済み]
    B -->|いいえ| D[配列を半分に分割]
    D --> E[左半分を取得]
    D --> F[右半分を取得]
    E --> G[左半分に対して
マージソートを再帰的に適用]
    F --> H[右半分に対して
マージソートを再帰的に適用]
    G --> I[ソートされた左半分と右半分をマージ]
    H --> I
    I --> J[ソートされた配列を返す]

flowchart TD
    subgraph マージ処理
    M1[左右の配列の先頭要素を比較] --> M2{左の要素 <= 右の要素?}
    M2 -->|はい| M3[左の要素を結果配列に追加
左配列のインデックスを進める]
    M2 -->|いいえ| M4[右の要素を結果配列に追加
右配列のインデックスを進める]
    M3 --> M5{両方の配列に要素が残っている?}
    M4 --> M5
    M5 -->|はい| M1
    M5 -->|いいえ| M6[残りの要素を全て結果配列に追加]
    M6 --> M7[結果配列を返す]
    end

より具体的な例は以下のとおりです。

graph TD
    A["入力配列: [38, 27, 43, 3, 9, 82, 10]"] --> B["分割: [38, 27, 43, 3] と [9, 82, 10]"]
    
    B --> C1["分割: [38, 27] と [43, 3]"]
    B --> C2["分割: [9, 82] と [10]"]
    
    C1 --> D1["分割: [38] と [27]"]
    C1 --> D2["分割: [43] と [3]"]
    C2 --> D3["分割: [9] と [82]"]
    C2 --> D4["[10]（単一要素）"]
    
    D1 --> E1["マージ: [27, 38]"]
    D2 --> E2["マージ: [3, 43]"]
    D3 --> E3["マージ: [9, 82]"]
    
    E1 --> F1["マージ: [3, 27, 38, 43]"]
    E2 --> F1
    E3 --> F2["マージ: [9, 10, 82]"]
    D4 --> F2
    
    F1 --> G["最終マージ: [3, 9, 10, 27, 38, 43, 82]"]
    F2 --> G
    
    style A fill:#f9f,stroke:#333,stroke-width:2px
    style G fill:#9f9,stroke:#333,stroke-width:2px
    
    subgraph "分割フェーズ (Divide)"
    B
    C1
    C2
    D1
    D2
    D3
    D4
    end
    
    subgraph "マージフェーズ (Merge)"
    E1
    E2
    E3
    F1
    F2
    end

3. マージソートの実装例（JavaScript）

より具体的な理解のために、JavaScriptでの実装例を示します：

function mergeSort(arr) {
  // 配列の長さが1以下の場合はそのまま返す
  if (arr.length <= 1) {
    return arr;
  }
  
  // 配列を半分に分割
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);
  
  // 分割した配列を再帰的にソート
  return merge(
    mergeSort(left),
    mergeSort(right)
  );
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;
  
  // 左右の配列を比較しながら小さい方から結果配列に追加
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }
  
  // 残りの要素を追加
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}