C#でマージソートを実装する方法をわかりやすく解説

マージソートとは

マージソート（Merge Sort）は、分割統治法を用いた代表的なソートアルゴリズムです。配列を半分ずつ2つの部分に分割し、それぞれの部分に対して再帰的に同じ処理を適用します。この分割と統合のプロセスを、配列全体がソート済みになるまで繰り返します。

マージソートは最悪の場合でも O(n log n) の計算量で動作するため、大規模なデータを安定してソートできる点が大きな特徴です。

C#によるマージソートの実装例

以下は、C#でマージソートを実装したプログラムの完全なサンプルコードです。

using System;
namespace QuickSortDemo {
    class Example {
        static public void merge(int[] arr, int p, int q, int r) {
            int i, j, k;
            int n1 = q - p + 1;
            int n2 = r - q;
            int[] L = new int[n1];
            int[] R = new int[n2];
            for (i = 0; i < n1; i++) {
                L[i] = arr[p + i];
            }
            for (j = 0; j < n2; j++) {
                R[j] = arr[q + 1 + j];
            }
            i = 0;
            j = 0;
            k = p;
            while (i < n1 && j < n2) {
                if (L[i] <= R[j]) {
                    arr[k] = L[i];
                    i++;
                } else {
                    arr[k] = R[j];
                    j++;
                }
                k++;
            }
            while (i < n1) {
                arr[k] = L[i];
                i++;
                k++;
            }
            while (j < n2) {
                arr[k] = R[j];
                j++;
                k++;
            }
        }
        static public void mergeSort(int[] arr, int p, int r) {
            if (p < r) {
                int q = (p + r) / 2;
                mergeSort(arr, p, q);
                mergeSort(arr, q + 1, r);
                merge(arr, p, q, r);
            }
        }
        static void Main(string[] args) {
            int[] arr = {76, 89, 23, 1, 55, 78, 99, 12, 65, 100};
            int n = 10, i;
            Console.WriteLine("Merge Sort");
            Console.Write("Initial array is: ");
            for (i = 0; i < n; i++) {
                Console.Write(arr[i] + " ");
            }
            mergeSort(arr, 0, n-1);
            Console.Write("\nSorted Array is: ");
            for (i = 0; i < n; i++) {
                Console.Write(arr[i] + " ");
            }
        }
    }
}

実行結果

上記のプログラムを実行すると、次のような出力が得られます。

Merge Sort
Initial array is: 76 89 23 1 55 78 99 12 65 100
Sorted Array is: 1 12 23 55 65 76 78 89 99 100

プログラムの解説

ここからは、上記のコードがどのように動作しているのかを順番に見ていきましょう。

Main() メソッドの処理

Main() メソッドでは、まず初期状態の配列をコンソールに表示し、その後 mergeSort() メソッドを呼び出して配列のソートを行います。該当するコード部分は以下の通りです。

int[] arr = {76, 89, 23, 1, 55, 78, 99, 12, 65, 100};
int n = 10, i;
Console.WriteLine("Merge Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
    Console.Write(arr[i] + " ");
}
mergeSort(arr, 0, n-1);

mergeSort() メソッドの処理

mergeSort() メソッドでは、まず変数 q を使って配列の中間地点を計算します。その後、分割された2つの部分配列それぞれに対して mergeSort() を再帰的に呼び出し、最後に merge() メソッドを呼び出して部分配列を統合します。該当するコード部分は以下の通りです。

if (p < r) {
    int q = (p + r) / 2;
    mergeSort(arr, p, q);
    mergeSort(arr, q + 1, r);
    merge(arr, p, q, r);
}

条件 p < r は、部分配列に要素が2つ以上存在する場合のみ処理を続行することを意味しています。要素が1つだけになった時点で再帰が終了し、統合フェーズへ移行します。

merge() メソッドの処理

merge() メソッドには、ソート済みの2つの部分配列が渡されます。このメソッドの役割は、これらの部分配列を比較しながら1つの配列に統合し、結果として得られる配列もソート済みの状態にすることです。該当するコード部分は以下の通りです。

int i, j, k;
int n1 = q - p + 1;
int n2 = r - q;
int[] L = new int[n1];
int[] R = new int[n2];
for (i = 0; i < n1; i++) {
    L[i] = arr[p + i];
}
for (j = 0; j < n2; j++) {
    R[j] = arr[q + 1 + j];
}
i = 0;
j = 0;
k = p;
while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
        arr[k] = L[i];
        i++;
    } else {
        arr[k] = R[j];
        j++;
    }
    k++;
}
while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
}
while (j < n2) {
    arr[k] = R[j];
    j++;
    k++;
}

まず、元の配列から左側の部分配列 L と右側の部分配列 R をコピーして作成します。その後、両方の部分配列の先頭要素を順番に比較し、小さい方から元の配列へ書き戻していきます。どちらか一方の部分配列が尽きた後は、残りの要素をそのまま末尾に追加します。

まとめ

マージソートは「分割」と「統合」を組み合わせたシンプルながら強力なアルゴリズムです。C#では再帰呼び出しを使うことで直感的に実装でき、データ量が多くても安定したパフォーマンスを発揮します。ソートアルゴリズムの学習や実務での利用において、ぜひ押さえておきたい基本テクニックの一つです。