Merge Sort
最終更新
マージソートは分割統治アルゴリズムです。各部分の要素が1つになる（それは自明にソート済み）まで配列を再帰的に半分に分割し、その後、部分を順序を保ちながら併合していきます。マージのステップでは2つのソート済み部分配列を2つのポインタでたどり、常に先頭のより小さい要素を次にコピーします。上の再生を押して、配列がマージごとに組み立て直される様子を見てみましょう。
常に半分に分割するため、マージソートはあらゆる場合で O(n log n) 時間で動作します。最悪の場合でも最良の場合と同じ良さです。その代償として、一時的なマージ用バッファに O(n) の追加空間を使います。
時間計算量と空間計算量
| ケース | 計算量 | 備考 |
|---|---|---|
| 最良の場合 | O(n log n) | 常に入力を半分にする |
| 平均の場合 | O(n log n) | ランダムな順序 |
| 最悪の場合 | O(n log n) | 保証あり - 不利な入力はない |
| 空間 | O(n) | マージ用の一時バッファ |
| 安定 | はい | 同値はマージ中に左側を優先して解決 |
ステップごとの手順
| ステップ | 何が起きるか |
|---|---|
| 1 | 範囲の要素が0個または1個なら、すでにソート済みです。 |
| 2 | 範囲を2つの半分に分割します。 |
| 3 | 左半分をマージソートで再帰的にソートします。 |
| 4 | 右半分をマージソートで再帰的にソートします。 |
| 5 | 2つのソート済みの半分を2つのポインタでマージします。 |
具体例
[5, 2, 4, 1] をソートする場合：
| パス | 配列 | 動作 |
|---|---|---|
| 分割 | [5, 2] | [4, 1] | 配列を2つの半分に分ける |
| 分割 | [5] [2] | [4] [1] | 各部分が単一要素になるまで再度分ける |
| マージ | [2, 5] | [1, 4] | [5],[2] を [2, 5] に、[4],[1] を [1, 4] にマージ |
| マージ | [1, 2, 4, 5] | [2, 5] と [1, 4] をマージ：1、次に 2、次に 4、次に 5 を選ぶ |
| 完了 | [1, 2, 4, 5] | 配列は完全にソート済み |
マージソートを使うべきとき
| 使うべきとき | 避けるべきとき |
|---|---|
保証された O(n log n) の最悪計算量が必要なとき | メモリが逼迫し、O(n) の追加空間が許容できないとき |
| 安定性が重要なとき（同じキーが順序を保つ） | 挿入ソートの方が速い小さな配列をソートするとき |
| 連結リストをソートするとき | その場ソートが厳しい要件のとき |
| データがRAMに収まらないほど大きいとき（外部ソート） | キャッシュ局所性が支配的で、quicksort のその場のパスが有利なとき |
Merge Sortのコード
Python, JavaScript, Java, C++, Cによるクリーンで実行可能なMerge Sortの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。
PythonでのMerge Sortのコード
Python
1def merge_sort(a):2 if len(a) <= 1:3 return a4 mid = len(a) // 25 left = merge_sort(a[:mid])6 right = merge_sort(a[mid:])7 return merge(left, right)8
9
10def merge(left, right):11 out = []12 i = j = 013 while i < len(left) and j < len(right):14 if left[i] <= right[j]:15 out.append(left[i])16 i += 117 else:18 out.append(right[j])19 j += 120 out.extend(left[i:])21 out.extend(right[j:])22 return out23
24
25nums = [38, 27, 43, 3, 9, 82, 10]26print("Before:", nums)27print("After: ", merge_sort(nums))JavaScriptでのMerge Sortのコード
JavaScript
1function mergeSort(arr) {2 if (arr.length <= 1) return arr;3 const mid = Math.floor(arr.length / 2);4 const left = mergeSort(arr.slice(0, mid));5 const right = mergeSort(arr.slice(mid));6 return merge(left, right);7}8
9// Merge two sorted arrays into one sorted array10function merge(left, right) {11 const out = [];12 let i = 0;13 let j = 0;14 while (i < left.length && j < right.length) {15 out.push(left[i] <= right[j] ? left[i++] : right[j++]);16 }17 return out.concat(left.slice(i), right.slice(j));18}19
20const data = [5, 2, 9, 1, 7, 3];21console.log("Before:", data);22console.log("Sorted:", mergeSort(data));JavaでのMerge Sortのコード
Java
1import java.util.Arrays;2
3public class Main {4 static void mergeSort(int[] arr, int left, int right) {5 if (left >= right) return;6 int mid = (left + right) / 2;7 mergeSort(arr, left, mid);8 mergeSort(arr, mid + 1, right);9 merge(arr, left, mid, right);10 }11
12 // Merge two sorted halves into a temp array, then copy back13 static void merge(int[] arr, int left, int mid, int right) {14 int[] tmp = new int[right - left + 1];15 int i = left, j = mid + 1, k = 0;16 while (i <= mid && j <= right) {17 tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];18 }19 while (i <= mid) tmp[k++] = arr[i++];20 while (j <= right) tmp[k++] = arr[j++];21 System.arraycopy(tmp, 0, arr, left, tmp.length);22 }23
24 public static void main(String[] args) {25 int[] arr = {38, 27, 43, 3, 9, 82, 10};26 System.out.println("Before: " + Arrays.toString(arr));27 mergeSort(arr, 0, arr.length - 1);28 System.out.println("After: " + Arrays.toString(arr));29 }30}C++でのMerge Sortのコード
C++
1#include <iostream>2#include <vector>3
4void printVec(const std::vector<int>& a) {5 for (int x : a) std::cout << x << " ";6 std::cout << "\n";7}8
9void merge(std::vector<int>& a, int lo, int mid, int hi) {10 std::vector<int> tmp;11 tmp.reserve(hi - lo + 1);12 int i = lo, j = mid + 1;13 while (i <= mid && j <= hi) {14 if (a[i] <= a[j]) tmp.push_back(a[i++]);15 else tmp.push_back(a[j++]);16 }17 while (i <= mid) tmp.push_back(a[i++]);18 while (j <= hi) tmp.push_back(a[j++]);19 for (size_t k = 0; k < tmp.size(); ++k) a[lo + k] = tmp[k];20}21
22void mergeSort(std::vector<int>& a, int lo, int hi) {23 if (lo >= hi) return;24 int mid = lo + (hi - lo) / 2;25 mergeSort(a, lo, mid); // sort the left half26 mergeSort(a, mid + 1, hi); // sort the right half27 merge(a, lo, mid, hi); // merge the sorted halves28}29
30int main() {31 std::vector<int> data = {38, 27, 43, 3, 9, 82, 10};32 std::cout << "Before: ";33 printVec(data);34 mergeSort(data, 0, static_cast<int>(data.size()) - 1);35 std::cout << "After: ";36 printVec(data);37 return 0;38}CでのMerge Sortのコード
C
1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5 for (int i = 0; i < n; i++) printf("%d ", a[i]);6 printf("\n");7}8
9void merge(int a[], int lo, int mid, int hi) {10 int* tmp = malloc((hi - lo + 1) * sizeof(int));11 int i = lo, j = mid + 1, k = 0;12 while (i <= mid && j <= hi) {13 if (a[i] <= a[j]) tmp[k++] = a[i++];14 else tmp[k++] = a[j++];15 }16 while (i <= mid) tmp[k++] = a[i++];17 while (j <= hi) tmp[k++] = a[j++];18 for (k = 0; k <= hi - lo; k++) a[lo + k] = tmp[k];19 free(tmp);20}21
22void mergeSort(int a[], int lo, int hi) {23 if (lo >= hi) return;24 int mid = lo + (hi - lo) / 2;25 mergeSort(a, lo, mid); // sort the left half26 mergeSort(a, mid + 1, hi); // sort the right half27 merge(a, lo, mid, hi); // merge the sorted halves28}29
30int main(void) {31 int data[] = {38, 27, 43, 3, 9, 82, 10};32 int n = sizeof(data) / sizeof(data[0]);33 printf("Before: ");34 printArr(data, n);35 mergeSort(data, 0, n - 1);36 printf("After: ");37 printArr(data, n);38 return 0;39}マージソートに関するよくある質問
マージソートの時間計算量は？
マージソートは常に配列を半分に分割するため、最良・平均・最悪のいずれの場合も
O(n log n) です。マージ用バッファに O(n) の追加空間を使います。マージソートは安定ですか？
はい、マージのステップが同値を左半分から先に取ることで解決する場合は安定です。これにより同じ要素は元の相対順序を保つため、マージソートは安定ソートの一般的な選択肢になっています。
なぜ quicksort ではなくマージソートを使うのですか？
マージソートは敵対的な入力でも
O(n log n) を保証し安定ですが、quicksort は O(n²) に劣化することがあります。マージソートは連結リストや外部ソートでも好まれます。欠点は O(n) の追加メモリです。マージソートと quicksort の違いは何ですか？
どちらも分割統治のソートですが、quicksort はピボットを軸に分割し
O(log n) のスタック空間でその場でソートするのに対し、マージソートは無条件に半分に分けて O(n) のバッファで併合します。quicksort はキャッシュ局所性のため実用上たいてい高速ですが、マージソートは保証された O(n log n) の最悪計算量を持ち安定です。実際にはいつマージソートを使うべきですか？
保証された
O(n log n) 上限を持つ安定ソートが必要なとき、連結リストをソートするとき（ランダムアクセスが不要）、あるいはメモリに収まらない大きなデータを外部ソートするときにマージソートを選びましょう。O(n) の追加空間を要するため、メモリが乏しいときは避けてください。マージソートはその場でソートしますか？
いいえ。標準的なマージソートは2つの半分を併合するために
O(n) の一時バッファを確保するため、その場（in-place）ではありません。その場マージの変種も存在しますが複雑で、遅くなるか安定性を失うため、バッファを用いる版が一般的な選択肢です。関連リソース
その他の可視化
