C言語でマージソートの最悪ケースを引き起こす順列を見つける方法

概要

与えられた要素の集合に対して、「どのような順列（並べ方）ならマージソートの最悪ケースになるか」を求めるのが本記事のテーマです。

マージソートは漸近的には常に O(n log n) の時間計算量で動作することが知られています。しかし、実際の処理時間は比較回数に大きく依存するため、比較回数が最も多くなる入力ほど、実行時間も長くなります。そこでここでは、標準的なマージソートアルゴリズムでソートした際に比較回数が最大となる入力順列を求めることを目指します。

例：

ソート済み配列として次の要素を考えます。
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

これに対して、マージソートの最悪ケースを引き起こす入力配列は次のようになります。
11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26

手法：ボトムアップ方式で配列を構築する

それでは、マージソートにとって最悪となる入力配列は、どのようにして求められるのでしょうか。ポイントは、配列をボトムアップ（下から上へ）の方向で組み立てることです。

まず、ソート済み配列を {11, 12, 13, 14, 15, 16, 17, 18} とします。

マージソートの最悪ケースを構築するには、最終的にこのソート済み配列を生み出したマージ操作が、最大の比較回数になるようにしなければなりません。そのためには、マージ操作の対象となる左部分配列と右部分配列が、ソート済み配列の交互の要素を持つように分割します。つまり、左部分配列を {11, 13, 15, 17}、右部分配列を {12, 14, 16, 18} とします。

こうすることで、配列内のすべての要素が最低1回は比較対象となり、比較回数が最大化されます。

さらに、同じ考え方を左右の部分配列にも再帰的に適用します。たとえば配列 {11, 13, 15, 17} の最悪ケースは、その左右の部分配列がそれぞれ {11, 15} と {13, 17} である場合に発生し、同様に配列 {12, 14, 16, 18} の場合には {12, 14} と {16, 18} の組み合わせで最悪ケースとなります。

完全なアルゴリズム

GenerateWorstCase(arr[])

• 2つの補助配列 left と right を作成し、元の配列の交互の要素をそれぞれに格納します。
• 左部分配列に対して GenerateWorstCase(left) を再帰的に呼び出します。
• 右部分配列に対して GenerateWorstCase(right) を再帰的に呼び出します。
• 最後に、left と right のすべての要素を元の配列へ書き戻します。

C言語による実装例

// マージソートの最悪ケースを生成するCプログラム
#include <stdlib.h>
#include <stdio.h>
// 配列を出力する関数
void printArray(int A1[], int size1){
    for (int i = 0; i < size1; i++)
        printf("%d ", A1[i]);
    printf("\n");
}
// 左右の部分配列を結合する関数
int join(int arr1[], int left1[], int right1[],
int l1, int m1, int r1){
    int i; // 次のループでも使用
    for (i = 0; i <= m1 - l1; i++)
        arr1[i] = left1[i];
    for (int j = 0; j < r1 - m1; j++)
        arr1[i + j] = right1[j];
}
// 交互の要素を左右の部分配列へ振り分ける関数
int split(int arr1[], int left1[], int right1[],
int l1, int m1, int r1){
    for (int i = 0; i <= m1 - l1; i++)
        left1[i] = arr1[i * 2];
    for (int i = 0; i < r1 - m1; i++)
        right1[i] = arr1[i * 2 + 1];
}
// マージソートの最悪ケースを生成する関数
int generateWorstCase(int arr1[], int l1, int r1){
    if (l1 < r1){
        int m1 = l1 + (r1 - l1) / 2;
        // 2つの補助配列を作成
        int left1[m1 - l1 + 1];
        int right1[r1 - m1];
        // 交互の要素を左右の部分配列に格納
        split(arr1, left1, right1, l1, m1, r1);
        // 前半と後半を再帰的に処理
        generateWorstCase(left1, l1, m1);
        generateWorstCase(right1, m1 + 1, r1);
        // 左右の部分配列を結合
        join(arr1, left1, right1, l1, m1, r1);
    }
}
// ドライバーコード
int main(){
    // ソート済み配列を初期化
    int arr1[] = { 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 };
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    printf("Sorted array is \n");
    printArray(arr1, n1);
    // マージソートの最悪ケースを生成
    generateWorstCase(arr1, 0, n1 - 1);
    printf("\nInput array that will result in " "worst case of merge sort is \n");
    printArray(arr1, n1);
    return 0;
}

実行結果

Sorted array is
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Input array that will result in worst case of merge sort is
11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26

まとめ

マージソートの最悪ケースは、各マージ段階で左右の部分配列が「交互に並んだ要素」を持つように入力を構成することで実現できます。この性質を利用すると、ソート済み配列から逆算して最悪ケースの順列を効率よく生成でき、アルゴリズムの計算量分析やベンチマークテストの入力データ作成などに役立ちます。