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] になります。

解法のアプローチ

この問題を解くには、次の手順に従います。

• merge() 関数を定義します。この関数は、配列 arr、配列 left、配列 right、l_index、m_index、r_index を引数に取ります。
• i を 0 で初期化し、i <= m_index - l_index を満たす間、i を 1 ずつ増やしながら次の処理を行います。
  • arr[i] := left[i]
• j を 0 で初期化し、j < r_index - m_index を満たす間、j を 1 ずつ増やしながら次の処理を行います。
  • arr[i + j] = right[j]
• divide() 関数を定義します。この関数は、配列 arr、配列 left、配列 right、l_index、m_index、r_index を引数に取ります。
• i を 0 で初期化し、i <= m_index - l_index を満たす間、i を 1 ずつ増やしながら次の処理を行います。
  • left[i] := arr[i * 2]
• i を 0 で初期化し、i < r_index - m_index を満たす間、i を 1 ずつ増やしながら次の処理を行います。
  • right[i] := arr[i * 2 + 1]
• gen_worst_seq() 関数を定義します。この関数は、配列 arr[]、l_index、r_index を引数に取ります。
• l_index < r_index である場合、次の処理を行います。
  • m_index := l_index + (r_index - l_index) / 2
  • サイズ m_index - l_index + 1 の配列 left を定義します。
  • サイズ r_index - m_index の配列 right を定義します。
  • divide(arr, left, right, l_index, m_index, r_index) を呼び出します。
  • gen_worst_seq(left, l_index, m_index) を呼び出します。
  • gen_worst_seq(right, m_index + 1, r_index) を呼び出します。
  • merge(arr, left, right, l_index, m_index, r_index) を呼び出します。

仕組みのポイント

このアルゴリズムでは、ソート済みの配列に対して再帰的に「偶数番目の要素」と「奇数番目の要素」への分割(divide)を適用し、その後マージ(merge)で元に戻しています。こうして得られる順列は、マージソートの各マージ段階において左右の部分配列の要素が交互に比較される状況を作り出し、比較回数を最大限に引き延ばします。その結果、マージソートにとって最悪のケースとなる入力順列が生成されます。

実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void display(int A[], int size) {
    for (int i = 0; i < size; i++)
        cout << A[i] << " ";
    cout << endl;
}
int merge(int arr[], int left[], int right[],int l_index, int m_index, int r_index) {
    int i;
    for (i = 0; i <= m_index - l_index; i++)
        arr[i] = left[i];
    for (int j = 0; j < r_index - m_index; j++)
        arr[i + j] = right[j];
}
int divide(int arr[], int left[], int right[], int l_index, int m_index, int r_index) {
    for (int i = 0; i <= m_index - l_index; i++)
        left[i] = arr[i * 2];
    for (int i = 0; i < r_index - m_index; i++)
        right[i] = arr[i * 2 + 1];
}
int gen_worst_seq(int arr[], int l_index, int r_index) {
    if (l_index < r_index) {
        int m_index = l_index + (r_index - l_index) / 2;
        int left[m_index - l_index + 1];
        int right[r_index - m_index];
        divide(arr, left, right, l_index, m_index, r_index);
        gen_worst_seq(left, l_index, m_index);
        gen_worst_seq(right, m_index + 1, r_index);
        merge(arr, left, right, l_index, m_index, r_index);
    }
}
int main() {
    int arr[] = {11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26};
    int n = sizeof(arr) / sizeof(arr[0]);
    gen_worst_seq(arr, 0, n - 1);
    display(arr, 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