マージソートは分割統治法に基づく効率的なソートアルゴリズムです。この記事では、C言語での実装方法とパフォーマンス向上のためのテクニックを解説します。

マージソートの基本概念

マージソートは配列を2つの部分に分割し、それぞれをソートした後、結果をマージするアルゴリズムです。以下の特徴があります：

• 時間計算量：O(n log n)
• 空間計算量：O(n)
• 安定ソート

基本実装

#include <stdio.h>
#include <stdlib.h>

void 統合(int 配列[], int 左, int 中央, int 右) {
    int 左サイズ = 中央 - 左 + 1;
    int 右サイズ = 右 - 中央;
    
    int *左配列 = malloc(左サイズ * sizeof(int));
    int *右配列 = malloc(右サイズ * sizeof(int));
    
    for (int i = 0; i < 左サイズ; i++)
        左配列[i] = 配列[左 + i];
    for (int j = 0; j < 右サイズ; j++)
        右配列[j] = 配列[中央 + 1 + j];
    
    int i = 0, j = 0, k = 左;
    while (i < 左サイズ && j < 右サイズ) {
        if (左配列[i] <= 右配列[j]) {
            配列[k] = 左配列[i];
            i++;
        } else {
            配列[k] = 右配列[j];
            j++;
        }
        k++;
    }
    
    while (i < 左サイズ) 配列[k++] = 左配列[i++];
    while (j < 右サイズ) 配列[k++] = 右配列[j++];
    
    free(左配列);
    free(右配列);
}

void マージソート(int 配列[], int 左, int 右) {
    if (左 < 右) {
        int 中央 = 左 + (右 - 左) / 2;
        マージソート(配列, 左, 中央);
        マージソート(配列, 中央 + 1, 右);
        統合(配列, 左, 中央, 右);
    }
}

最適化手法

1. 一時配列の再利用

void 最適化統合(int 配列[], int 左, int 中央, int 右, int 一時配列[]) {
    // 最適化された統合処理
}

void 最適化マージソート(int 配列[], int 左, int 右, int 一時配列[]) {
    if (右 - 左 < 15) {
        // 挿入ソートを使用
    } else {
        int 中央 = 左 + (右 - 左) / 2;
        最適化マージソート(配列, 左, 中央, 一時配列);
        最適化マージソート(配列, 中央 + 1, 右, 一時配列);
        最適化統合(配列, 左, 中央, 右, 一時配列);
    }
}

2. 小規模配列での挿入ソートの採用

再帰の深さが浅い場合、挿入ソートに切り替えることでパフォーマンスを向上させます。

応用例

• 大規模データセットの処理
• 外部ソート（ディスク上のデータソート）
• 並列処理環境でのソート