配列の転倒数（Inversion Count）をマージソートで効率的に求める方法

配列の転倒数（Inversion Count）とは、配列をソート済みの状態（昇順）へ変換するために必要な入れ替えの回数を表す指標です。添字のペア (i, j) について i < j かつ arr[i] > arr[j] が成り立つとき、そのペアは「転倒（反転）」していると定義されます。

配列がすでにソートされていれば転倒数は 0 になり、逆に配列が完全に逆順（降順）に並んでいる場合は転倒数が最大になります。

すべてのペアを総当たりで調べる素朴なアプローチでは O(n²) の計算量が必要ですが、マージソートを応用した分割統治法（Divide and Conquer）を用いることで、計算量を O(n log n) まで削減できます。本記事ではそのアルゴリズムと C++ 実装例を紹介します。

入力と出力

入力：
数列 (1, 5, 6, 4, 20)

出力：
数値を昇順に並べるために必要な転倒（入れ替え）の回数

この例での転倒数は 2 です。
1 回目の転倒：(1, 5, 4, 6, 20)
2 回目の転倒：(1, 4, 5, 6, 20)

アルゴリズム

merge 関数

入力：マージ対象となる2つの部分配列と、left・mid・right の各インデックス
出力：ソート済みの順序でマージされた配列

Begin
    i := left
    j := mid
    k := left
    count := 0

    while i <= mid - 1 かつ j <= right の間、繰り返す
        if array[i] <= array[j] then
            tempArray[k] := array[i]
            i と k を 1 ずつ増やす
        else
            tempArray[k] := array[j]
            j と k を 1 ずつ増やす
            count := count + (mid - i)   // 左側に残る要素数ぶん反転が発生
    done

    // 左側の部分配列に余った要素がある場合
    while i <= mid - 1
        tempArray[k] := array[i]
        i と k を 1 ずつ増やす
    done

    // 右側の部分配列に余った要素がある場合
    while j <= right
        tempArray[k] := array[j]
        j と k を 1 ずつ増やす
    done

    return count
End

ポイントは、右側の要素が左側の要素より小さいときに count += (mid - i) を実行する箇所です。左側の部分配列はすでにソートされているため、そこに残っている要素はすべて現在の右側要素よりも大きく、これらが一括して反転としてカウントできます。

mergeSort 関数

入力：対象の配列と作業用配列、および配列の左端・右端のインデックス
出力：ソート完了時の転倒数

Begin
    count := 0
    if right > left then
        mid := (right + left) / 2
        count := mergeSort(array, tempArray, left, mid)
        count := count + mergeSort(array, tempArray, mid+1, right)
        count := count + merge(array, tempArray, left, mid+1, right)
    return count
End

配列を半分ずつ再帰的に分割しながら、左半分・右半分それぞれの転倒数を求め、最後にマージ時に発生する「左右間の転倒」を合計することで、全体の転倒数が得られます。

C++ による実装例

#include <iostream>
using namespace std;

int merge(int arr[], int temp[], int left, int mid, int right) {
    int i, j, k;
    int count = 0;

    i = left;    // 左側配列の位置を指す
    j = mid;     // 右側配列の位置を指す
    k = left;    // マージ後の配列の位置を指す

    while ((i <= mid - 1) && (j <= right)) {
        if (arr[i] <= arr[j]) {   // 左側の要素が右側以下の場合
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            count += (mid - i);   // 発生した反転の数を加算
        }
    }

    while (i <= mid - 1)      // 左側に残り要素があれば追加
        temp[k++] = arr[i++];

    while (j <= right)        // 右側に残り要素があれば追加
        temp[k++] = arr[j++];

    for (i = left; i <= right; i++)
        arr[i] = temp[i];     // 作業用配列を元の配列へ書き戻す

    return count;
}

int mergeSort(int arr[], int temp[], int left, int right) {
    int mid, count = 0;

    if (right > left) {
        mid = (right + left) / 2;                      // 配列の中央インデックスを求める
        count  = mergeSort(arr, temp, left, mid);      // 左側の部分配列をソート
        count += mergeSort(arr, temp, mid + 1, right); // 右側の部分配列をソート

        count += merge(arr, temp, left, mid + 1, right); // 2つの部分配列をマージ
    }
    return count;
}

int arrInversion(int arr[], int n) {
    int temp[n];
    return mergeSort(arr, temp, 0, n - 1);
}

int main() {
    int arr[] = {1, 5, 6, 4, 20};
    int n = 5;
    cout << "Number of inversions are " << arrInversion(arr, n);
}

実行結果

Number of inversions are 2

計算量

• 時間計算量：O(n log n) ― マージソートと同様に、分割が log n 段階、各段階のマージで O(n) かかるためです。
• 空間計算量：O(n) ― マージ用の作業用配列が必要になります。

総当たり法（O(n²)）と比べて大幅に高速であり、大規模なデータセットでも実用的に転倒数を求められます。