C言語で学ぶマージソートの仕組みと実装方法

ソート（整列）とは、データの要素を昇順または降順に並べ替える処理のことです。本記事では、C言語における代表的なソート手法のひとつである「マージソート」について、その基本概念から実際のコードによる実装方法まで、初心者にもわかるように丁寧に解説します。

C言語で使われる主なソート手法

C言語では、主に以下の5つのソート手法が広く知られています。

• バブルソート（交換ソート）
• 選択ソート
• 挿入ソート（線形ソート）
• クイックソート（分割交換ソート）
• マージソート（外部ソート）

マージソートとは

マージソートは「分割統治法（Divide and Conquer）」に基づいたソートアルゴリズムです。配列を半分ずつに分割していき、それぞれの部分を再帰的に整列させ、最後にそれらをマージ（結合）することで、完全にソートされた配列を作り上げます。

動作例

ここで、次の未ソートの配列に対してマージソートを適用してみましょう。

38, 27, 43, 3, 9, 82, 10

まず配列を細かく分割し、その後、整列しながら順番に結合していく様子は下図のようになります。

計算量の特徴

マージソートの最大の特徴は、データの初期状態にかかわらず、常に O(n log n) の計算量で安定した性能を発揮できる点です。ただし、マージ時に作業用の一時配列が必要となるため、追加のメモリ領域を消費する点には注意が必要です。

サンプルプログラム

以下は、マージソートの手法を使って配列の要素を昇順に並べ替えるC言語プログラムです。

#include <stdio.h>
#define max 10
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];
void merging(int low, int mid, int high) {
   int l1, l2, i;
   for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
      if(a[l1] <= a[l2])
         b[i] = a[l1++];
      else
         b[i] = a[l2++];
   }
   while(l1 <= mid)
      b[i++] = a[l1++];
   while(l2 <= high)
      b[i++] = a[l2++];
   for(i = low; i <= high; i++)
      a[i] = b[i];
   }
   void sort(int low, int high) {
      int mid;
      if(low < high) {
         mid = (low + high) / 2;
         sort(low, mid);
         sort(mid+1, high);
         merging(low, mid, high);
      } else {
      return;
   }
}
int main() {
   int i;
   printf("List before sorting\n");
   for(i = 0; i <= max; i++)
   printf("%d ", a[i]);
   sort(0, max);
   printf("\nList after sorting\n");
   for(i = 0; i <= max; i++)
   printf("%d ", a[i]);
}

実行結果

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。

List before sorting
10 14 19 26 27 31 33 35 42 44 0
List after sorting
0 10 14 19 26 27 31 33 35 42 44

実行結果を見ると、ソート前は末尾にあった「0」も含めて、すべての要素が正しく昇順に並べ替えられていることが確認できます。マージソートは大規模なデータセットに対しても高いパフォーマンスを発揮するため、実務においても非常に有用なアルゴリズムといえます。