コンテンツにスキップ

11.6   マージソート

マージソート（merge sort）は分割統治戦略に基づくソートアルゴリズムであり、以下の図に示す「分割」と「マージ」の段階から構成されます。

  1. 分割段階：再帰によって配列を中点で繰り返し分割し、長い配列のソート問題を短い配列のソート問題へ変換します。
  2. マージ段階：部分配列の長さが 1 になったら分割を終了し、マージを開始して、左右 2 つの短いソート済み配列をより長いソート済み配列へと繰り返しマージしていきます。

マージソートの分割とマージの段階

図 11-10   マージソートの分割とマージの段階

11.6.1   アルゴリズムの流れ

以下の図に示すように、「分割段階」では配列を上から下へ再帰的に中点で 2 つの部分配列へ分割します。

  1. 配列の中点 mid を計算し、左部分配列（区間 [left, mid] ）と右部分配列（区間 [mid + 1, right] ）を再帰的に分割します。
  2. 手順 1. を再帰的に実行し、部分配列区間の長さが 1 になった時点で終了します。

「マージ段階」では左部分配列と右部分配列を下から上へとマージし、1 つのソート済み配列にします。長さ 1 の部分配列からマージを始めるため、この段階の各部分配列はすでに整列されています。

マージソートの手順

merge_sort_step2

merge_sort_step3

merge_sort_step4

merge_sort_step5

merge_sort_step6

merge_sort_step7

merge_sort_step8

merge_sort_step9

merge_sort_step10

図 11-11   マージソートの手順

観察すると、マージソートの再帰順序は二分木の後順走査と一致していることがわかります。

  • 後順走査：まず左部分木を再帰し、次に右部分木を再帰し、最後に根ノードを処理します。
  • マージソート：まず左部分配列を再帰し、次に右部分配列を再帰し、最後にマージを処理します。

マージソートの実装を以下のコードに示します。注意として、nums のマージ対象区間は [left, right] であり、tmp の対応区間は [0, right - left] です。

merge_sort.py
def merge(nums: list[int], left: int, mid: int, right: int):
    """左部分配列と右部分配列をマージ"""
    # 左部分配列の区間は [left, mid]、右部分配列の区間は [mid+1, right]
    # マージ結果を格納する一時配列 tmp を作成
    tmp = [0] * (right - left + 1)
    # 左右の部分配列の開始インデックスを初期化する
    i, j, k = left, mid + 1, 0
    # 左右の部分配列にまだ要素がある間は比較し、小さいほうを一時配列にコピーする
    while i <= mid and j <= right:
        if nums[i] <= nums[j]:
            tmp[k] = nums[i]
            i += 1
        else:
            tmp[k] = nums[j]
            j += 1
        k += 1
    # 左右の部分配列の残り要素を一時配列にコピーする
    while i <= mid:
        tmp[k] = nums[i]
        i += 1
        k += 1
    while j <= right:
        tmp[k] = nums[j]
        j += 1
        k += 1
    # 一時配列 tmp の要素を元の配列 nums の対応区間にコピーする
    for k in range(0, len(tmp)):
        nums[left + k] = tmp[k]

def merge_sort(nums: list[int], left: int, right: int):
    """マージソート"""
    # 終了条件
    if left >= right:
        return  # 部分配列の長さが 1 になったら再帰を終了
    # 分割フェーズ
    mid = (left + right) // 2 # 中点を計算
    merge_sort(nums, left, mid)  # 左部分配列を再帰処理
    merge_sort(nums, mid + 1, right)  # 右部分配列を再帰処理
    # マージフェーズ
    merge(nums, left, mid, right)
merge_sort.cpp
/* 左部分配列と右部分配列をマージ */
void merge(vector<int> &nums, int left, int mid, int right) {
    // 左部分配列の区間は [left, mid]、右部分配列の区間は [mid+1, right]
    // マージ結果を格納する一時配列 tmp を作成
    vector<int> tmp(right - left + 1);
    // 左右の部分配列の開始インデックスを初期化する
    int i = left, j = mid + 1, k = 0;
    // 左右の部分配列にまだ要素がある間は比較し、小さいほうを一時配列にコピーする
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j])
            tmp[k++] = nums[i++];
        else
            tmp[k++] = nums[j++];
    }
    // 左右の部分配列の残り要素を一時配列にコピーする
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    // 一時配列 tmp の要素を元の配列 nums の対応区間にコピーする
    for (k = 0; k < tmp.size(); k++) {
        nums[left + k] = tmp[k];
    }
}

/* マージソート */
void mergeSort(vector<int> &nums, int left, int right) {
    // 終了条件
    if (left >= right)
        return; // 部分配列の長さが 1 になったら再帰を終了
    // 分割フェーズ
    int mid = left + (right - left) / 2;    // 中点を計算
    mergeSort(nums, left, mid);      // 左部分配列を再帰処理
    mergeSort(nums, mid + 1, right); // 右部分配列を再帰処理
    // マージフェーズ
    merge(nums, left, mid, right);
}
merge_sort.java
/* 左部分配列と右部分配列をマージ */
void merge(int[] nums, int left, int mid, int right) {
    // 左部分配列の区間は [left, mid]、右部分配列の区間は [mid+1, right]
    // マージ結果を格納する一時配列 tmp を作成
    int[] tmp = new int[right - left + 1];
    // 左右の部分配列の開始インデックスを初期化する
    int i = left, j = mid + 1, k = 0;
    // 左右の部分配列にまだ要素がある間は比較し、小さいほうを一時配列にコピーする
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j])
            tmp[k++] = nums[i++];
        else
            tmp[k++] = nums[j++];
    }
    // 左右の部分配列の残り要素を一時配列にコピーする
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    // 一時配列 tmp の要素を元の配列 nums の対応区間にコピーする
    for (k = 0; k < tmp.length; k++) {
        nums[left + k] = tmp[k];
    }
}

/* マージソート */
void mergeSort(int[] nums, int left, int right) {
    // 終了条件
    if (left >= right)
        return; // 部分配列の長さが 1 になったら再帰を終了
    // 分割フェーズ
    int mid = left + (right - left) / 2; // 中点を計算
    mergeSort(nums, left, mid); // 左部分配列を再帰処理
    mergeSort(nums, mid + 1, right); // 右部分配列を再帰処理
    // マージフェーズ
    merge(nums, left, mid, right);
}
merge_sort.cs
/* 左部分配列と右部分配列をマージ */
void Merge(int[] nums, int left, int mid, int right) {
    // 左部分配列の区間は [left, mid]、右部分配列の区間は [mid+1, right]
    // マージ結果を格納する一時配列 tmp を作成
    int[] tmp = new int[right - left + 1];
    // 左右の部分配列の開始インデックスを初期化する
    int i = left, j = mid + 1, k = 0;
    // 左右の部分配列にまだ要素がある間は比較し、小さいほうを一時配列にコピーする
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j])
            tmp[k++] = nums[i++];
        else
            tmp[k++] = nums[j++];
    }
    // 左右の部分配列の残り要素を一時配列にコピーする
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    // 一時配列 tmp の要素を元の配列 nums の対応区間にコピーする
    for (k = 0; k < tmp.Length; ++k) {
        nums[left + k] = tmp[k];
    }
}

/* マージソート */
void MergeSort(int[] nums, int left, int right) {
    // 終了条件
    if (left >= right) return;       // 部分配列の長さが 1 になったら再帰を終了
    // 分割フェーズ
    int mid = left + (right - left) / 2;    // 中点を計算
    MergeSort(nums, left, mid);      // 左部分配列を再帰処理
    MergeSort(nums, mid + 1, right); // 右部分配列を再帰処理
    // マージフェーズ
    Merge(nums, left, mid, right);
}
merge_sort.go
/* 左部分配列と右部分配列をマージ */
func merge(nums []int, left, mid, right int) {
    // 左部分配列の区間は [left, mid]、右部分配列の区間は [mid+1, right]
    // マージ結果を格納する一時配列 tmp を作成
    tmp := make([]int, right-left+1)
    // 左右の部分配列の開始インデックスを初期化する
    i, j, k := left, mid+1, 0
    // 左右の部分配列にまだ要素がある間は比較し、小さいほうを一時配列にコピーする
    for i <= mid && j <= right {
        if nums[i] <= nums[j] {
            tmp[k] = nums[i]
            i++
        } else {
            tmp[k] = nums[j]
            j++
        }
        k++
    }
    // 左右の部分配列の残り要素を一時配列にコピーする
    for i <= mid {
        tmp[k] = nums[i]
        i++
        k++
    }
    for j <= right {
        tmp[k] = nums[j]
        j++
        k++
    }
    // 一時配列 tmp の要素を元の配列 nums の対応区間にコピーする
    for k := 0; k < len(tmp); k++ {
        nums[left+k] = tmp[k]
    }
}

/* マージソート */
func mergeSort(nums []int, left, right int) {
    // 終了条件
    if left >= right {
        return
    }
    // 分割フェーズ
    mid := left + (right - left) / 2
    mergeSort(nums, left, mid)
    mergeSort(nums, mid+1, right)
    // マージフェーズ
    merge(nums, left, mid, right)
}
merge_sort.swift
/* 左部分配列と右部分配列をマージ */
func merge(nums: inout [Int], left: Int, mid: Int, right: Int) {
    // 左部分配列の区間は [left, mid]、右部分配列の区間は [mid+1, right]
    // マージ結果を格納する一時配列 tmp を作成
    var tmp = Array(repeating: 0, count: right - left + 1)
    // 左右の部分配列の開始インデックスを初期化する
    var i = left, j = mid + 1, k = 0
    // 左右の部分配列にまだ要素がある間は比較し、小さいほうを一時配列にコピーする
    while i <= mid, j <= right {
        if nums[i] <= nums[j] {
            tmp[k] = nums[i]
            i += 1
        } else {
            tmp[k] = nums[j]
            j += 1
        }
        k += 1
    }
    // 左右の部分配列の残り要素を一時配列にコピーする
    while i <= mid {
        tmp[k] = nums[i]
        i += 1
        k += 1
    }
    while j <= right {
        tmp[k] = nums[j]
        j += 1
        k += 1
    }
    // 一時配列 tmp の要素を元の配列 nums の対応区間にコピーする
    for k in tmp.indices {
        nums[left + k] = tmp[k]
    }
}

/* マージソート */
func mergeSort(nums: inout [Int], left: Int, right: Int) {
    // 終了条件
    if left >= right { // 部分配列の長さが 1 になったら再帰を終了
        return
    }
    // 分割フェーズ
    let mid = left + (right - left) / 2 // 中点を計算
    mergeSort(nums: &nums, left: left, right: mid) // 左部分配列を再帰処理
    mergeSort(nums: &nums, left: mid + 1, right: right) // 右部分配列を再帰処理
    // マージフェーズ
    merge(nums: &nums, left: left, mid: mid, right: right)
}
merge_sort.js
/* 左部分配列と右部分配列をマージ */
function merge(nums, left, mid, right) {
    // 左部分配列の区間は [left, mid]、右部分配列の区間は [mid+1, right]
    // マージ結果を格納する一時配列 tmp を作成
    const tmp = new Array(right - left + 1);
    // 左右の部分配列の開始インデックスを初期化する
    let i = left,
        j = mid + 1,
        k = 0;
    // 左右の部分配列にまだ要素がある間は比較し、小さいほうを一時配列にコピーする
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            tmp[k++] = nums[i++];
        } else {
            tmp[k++] = nums[j++];
        }
    }
    // 左右の部分配列の残り要素を一時配列にコピーする
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    // 一時配列 tmp の要素を元の配列 nums の対応区間にコピーする
    for (k = 0; k < tmp.length; k++) {
        nums[left + k] = tmp[k];
    }
}

/* マージソート */
function mergeSort(nums, left, right) {
    // 終了条件
    if (left >= right) return; // 部分配列の長さが 1 になったら再帰を終了
    // 分割フェーズ
    let mid = Math.floor(left + (right - left) / 2); // 中点を計算
    mergeSort(nums, left, mid); // 左部分配列を再帰処理
    mergeSort(nums, mid + 1, right); // 右部分配列を再帰処理
    // マージフェーズ
    merge(nums, left, mid, right);
}
merge_sort.ts
/* 左部分配列と右部分配列をマージ */
function merge(nums: number[], left: number, mid: number, right: number): void {
    // 左部分配列の区間は [left, mid]、右部分配列の区間は [mid+1, right]
    // マージ結果を格納する一時配列 tmp を作成
    const tmp = new Array(right - left + 1);
    // 左右の部分配列の開始インデックスを初期化する
    let i = left,
        j = mid + 1,
        k = 0;
    // 左右の部分配列にまだ要素がある間は比較し、小さいほうを一時配列にコピーする
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            tmp[k++] = nums[i++];
        } else {
            tmp[k++] = nums[j++];
        }
    }
    // 左右の部分配列の残り要素を一時配列にコピーする
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    // 一時配列 tmp の要素を元の配列 nums の対応区間にコピーする
    for (k = 0; k < tmp.length; k++) {
        nums[left + k] = tmp[k];
    }
}

/* マージソート */
function mergeSort(nums: number[], left: number, right: number): void {
    // 終了条件
    if (left >= right) return; // 部分配列の長さが 1 になったら再帰を終了
    // 分割フェーズ
    let mid = Math.floor(left + (right - left) / 2); // 中点を計算
    mergeSort(nums, left, mid); // 左部分配列を再帰処理
    mergeSort(nums, mid + 1, right); // 右部分配列を再帰処理
    // マージフェーズ
    merge(nums, left, mid, right);
}
merge_sort.dart
/* 左部分配列と右部分配列をマージ */
void merge(List<int> nums, int left, int mid, int right) {
  // 左部分配列の区間は [left, mid]、右部分配列の区間は [mid+1, right]
  // マージ結果を格納する一時配列 tmp を作成
  List<int> tmp = List.filled(right - left + 1, 0);
  // 左右の部分配列の開始インデックスを初期化する
  int i = left, j = mid + 1, k = 0;
  // 左右の部分配列にまだ要素がある間は比較し、小さいほうを一時配列にコピーする
  while (i <= mid && j <= right) {
    if (nums[i] <= nums[j])
      tmp[k++] = nums[i++];
    else
      tmp[k++] = nums[j++];
  }
  // 左右の部分配列の残り要素を一時配列にコピーする
  while (i <= mid) {
    tmp[k++] = nums[i++];
  }
  while (j <= right) {
    tmp[k++] = nums[j++];
  }
  // 一時配列 tmp の要素を元の配列 nums の対応区間にコピーする
  for (k = 0; k < tmp.length; k++) {
    nums[left + k] = tmp[k];
  }
}

/* マージソート */
void mergeSort(List<int> nums, int left, int right) {
  // 終了条件
  if (left >= right) return; // 部分配列の長さが 1 になったら再帰を終了
  // 分割フェーズ
  int mid = left + (right - left) ~/ 2; // 中点を計算
  mergeSort(nums, left, mid); // 左部分配列を再帰処理
  mergeSort(nums, mid + 1, right); // 右部分配列を再帰処理
  // マージフェーズ
  merge(nums, left, mid, right);
}
merge_sort.rs
/* 左部分配列と右部分配列をマージ */
fn merge(nums: &mut [i32], left: usize, mid: usize, right: usize) {
    // 左部分配列の区間は [left, mid]、右部分配列の区間は [mid+1, right]
    // マージ結果を格納する一時配列 tmp を作成
    let tmp_size = right - left + 1;
    let mut tmp = vec![0; tmp_size];
    // 左右の部分配列の開始インデックスを初期化する
    let (mut i, mut j, mut k) = (left, mid + 1, 0);
    // 左右の部分配列にまだ要素がある間は比較し、小さいほうを一時配列にコピーする
    while i <= mid && j <= right {
        if nums[i] <= nums[j] {
            tmp[k] = nums[i];
            i += 1;
        } else {
            tmp[k] = nums[j];
            j += 1;
        }
        k += 1;
    }
    // 左右の部分配列の残り要素を一時配列にコピーする
    while i <= mid {
        tmp[k] = nums[i];
        k += 1;
        i += 1;
    }
    while j <= right {
        tmp[k] = nums[j];
        k += 1;
        j += 1;
    }
    // 一時配列 tmp の要素を元の配列 nums の対応区間にコピーする
    for k in 0..tmp_size {
        nums[left + k] = tmp[k];
    }
}

/* マージソート */
fn merge_sort(nums: &mut [i32], left: usize, right: usize) {
    // 終了条件
    if left >= right {
        return; // 部分配列の長さが 1 になったら再帰を終了
    }

    // 分割フェーズ
    let mid = left + (right - left) / 2; // 中点を計算
    merge_sort(nums, left, mid); // 左部分配列を再帰処理
    merge_sort(nums, mid + 1, right); // 右部分配列を再帰処理

    // マージフェーズ
    merge(nums, left, mid, right);
}
merge_sort.c
/* 左部分配列と右部分配列をマージ */
void merge(int *nums, int left, int mid, int right) {
    // 左部分配列の区間は [left, mid]、右部分配列の区間は [mid+1, right]
    // マージ結果を格納する一時配列 tmp を作成
    int tmpSize = right - left + 1;
    int *tmp = (int *)malloc(tmpSize * sizeof(int));
    // 左右の部分配列の開始インデックスを初期化する
    int i = left, j = mid + 1, k = 0;
    // 左右の部分配列にまだ要素がある間は比較し、小さいほうを一時配列にコピーする
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            tmp[k++] = nums[i++];
        } else {
            tmp[k++] = nums[j++];
        }
    }
    // 左右の部分配列の残り要素を一時配列にコピーする
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    // 一時配列 tmp の要素を元の配列 nums の対応区間にコピーする
    for (k = 0; k < tmpSize; ++k) {
        nums[left + k] = tmp[k];
    }
    // メモリを解放する
    free(tmp);
}

/* マージソート */
void mergeSort(int *nums, int left, int right) {
    // 終了条件
    if (left >= right)
        return; // 部分配列の長さが 1 になったら再帰を終了
    // 分割フェーズ
    int mid = left + (right - left) / 2;    // 中点を計算
    mergeSort(nums, left, mid);      // 左部分配列を再帰処理
    mergeSort(nums, mid + 1, right); // 右部分配列を再帰処理
    // マージフェーズ
    merge(nums, left, mid, right);
}
merge_sort.kt
/* 左部分配列と右部分配列をマージ */
fun merge(nums: IntArray, left: Int, mid: Int, right: Int) {
    // 左部分配列の区間は [left, mid]、右部分配列の区間は [mid+1, right]
    // マージ結果を格納する一時配列 tmp を作成
    val tmp = IntArray(right - left + 1)
    // 左右の部分配列の開始インデックスを初期化する
    var i = left
    var j = mid + 1
    var k = 0
    // 左右の部分配列にまだ要素がある間は比較し、小さいほうを一時配列にコピーする
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j])
            tmp[k++] = nums[i++]
        else
            tmp[k++] = nums[j++]
    }
    // 左右の部分配列の残り要素を一時配列にコピーする
    while (i <= mid) {
        tmp[k++] = nums[i++]
    }
    while (j <= right) {
        tmp[k++] = nums[j++]
    }
    // 一時配列 tmp の要素を元の配列 nums の対応区間にコピーする
    for (l in tmp.indices) {
        nums[left + l] = tmp[l]
    }
}

/* マージソート */
fun mergeSort(nums: IntArray, left: Int, right: Int) {
    // 終了条件
    if (left >= right) return  // 部分配列の長さが 1 になったら再帰を終了
    // 分割フェーズ
    val mid = left + (right - left) / 2 // 中点を計算
    mergeSort(nums, left, mid) // 左部分配列を再帰処理
    mergeSort(nums, mid + 1, right) // 右部分配列を再帰処理
    // マージフェーズ
    merge(nums, left, mid, right)
}
merge_sort.rb
### 左部分配列と右部分配列をマージ ###
def merge(nums, left, mid, right)
  # 左部分配列の区間は [left, mid]、右部分配列の区間は [mid+1, right]
  # マージ結果を格納する一時配列 tmp を作成
  tmp = Array.new(right - left + 1, 0)
  # 左右の部分配列の開始インデックスを初期化する
  i, j, k = left, mid + 1, 0
  # 左右の部分配列にまだ要素がある間は比較し、小さいほうを一時配列にコピーする
  while i <= mid && j <= right
    if nums[i] <= nums[j]
      tmp[k] = nums[i]
      i += 1
    else
      tmp[k] = nums[j]
      j += 1
    end
    k += 1
  end
  # 左右の部分配列の残り要素を一時配列にコピーする
  while i <= mid
    tmp[k] = nums[i]
    i += 1
    k += 1
  end
  while j <= right
    tmp[k] = nums[j]
    j += 1
    k += 1
  end
  # 一時配列 tmp の要素を元の配列 nums の対応区間にコピーする
  (0...tmp.length).each do |k|
    nums[left + k] = tmp[k]
  end
end

### マージソート ###
def merge_sort(nums, left, right)
  # 終了条件
  # 部分配列の長さが 1 になったら再帰を終了する
  return if left >= right
  # 分割フェーズ
  mid = left + (right - left) / 2 # 中点を計算
  merge_sort(nums, left, mid) # 左部分配列を再帰処理
  merge_sort(nums, mid + 1, right) # 右部分配列を再帰処理
  # マージフェーズ
  merge(nums, left, mid, right)
end
コードの可視化

11.6.2   アルゴリズムの特性

  • 時間計算量は \(O(n \log n)\)、非適応型ソート：分割によって高さ \(\log n\) の再帰木が生成され、各層でのマージ操作の総数は \(n\) であるため、全体の時間計算量は \(O(n \log n)\) です。
  • 空間計算量は \(O(n)\)、インプレースではないソート：再帰の深さは \(\log n\) であり、サイズ \(O(\log n)\) のスタックフレーム領域を使用します。マージ操作は補助配列を用いて実装する必要があり、サイズ \(O(n)\) の追加領域を使用します。
  • 安定ソート：マージの過程では、等しい要素の順序は変化しません。

11.6.3   連結リストのソート

連結リストに対しては、マージソートは他のソートアルゴリズムと比べて顕著な利点があり、連結リストのソート問題の空間計算量を \(O(1)\) まで最適化できます 。

  • 分割段階：連結リストの分割は「再帰」の代わりに「反復」で実装できるため、再帰で使用するスタックフレーム領域を省けます。
  • マージ段階：連結リストでは、ノードの追加や削除は参照（ポインタ）を変更するだけで実現できるため、マージ段階（2 つの短いソート済み連結リストを 1 つの長いソート済み連結リストにマージすること）では追加の連結リストを作成する必要がありません。

具体的な実装の詳細は比較的複雑なので、興味のある読者は関連資料を参照して学習してください。

ご意見、ご質問、ご提案があればぜひコメントしてください