ALDS1_5_D 反転数をC++で解いてみた[AIZU ONLINE JUDGE]

こんにちは！ mnbd（@mnbbbbbd）です。

プログラミング初心者なので、もっといい回答があるに違いありません。

あくまでも「動作はする」サンプルとしてご覧ください。

問題文
解答
感想
まとめ

問題文

数列 A={a0,a1,…an−1} について、ai>aj かつ i<j である組 (i,j) の個数を反転数と言います。反転数は次のバブルソートの交換回数と等しくなります。
（バブルソートのコードは、以下のリンク先のサイトにあります）
数列 A が与えられるので、A の反転数を求めてください。上の疑似コードのアルゴリズムをそのまま実装するとTime Limit Exceeded になることに注意してください。
入力
１行目に数列 A の長さ n が与えられます。２行目に ai(i=0,1,..n−1) が空白区切りで与えられます。
出力
反転数を１行に出力してください。
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_D

解答

#include <bits/stdc++.h>
using namespace std;

long long int sum = 0;

int bubble_sort(int a[], int n) {
    int cnt = 0;
    for(int i = 0; i < n; i++) {
        for(int j = n - 1; j > 0; j--) {
            if(a[j] < a[j - 1]) {
                swap(a[j], a[j - 1]);
                cnt++;
            }
        }
    }
    return cnt;
}

void merge(int a[], int left, int mid, int right) {
    int n1 = mid - left;
    int n2 = right - mid;
    int l[n1 + 1], r[n2 + 1];
    for(int i = 0; i < n1; i++) {
        l[i] = a[left + i];
    }
    for(int i = 0; i < n2; i++) {
        r[i] = a[mid + i];
    }
    l[n1] = r[n2] = INT_MAX;

    int i = 0, j = 0;
    for(int k = left; k < right; k++) {
        if(l[i] < r[j]) {
            a[k] = l[i++];
        } else {
            a[k] = r[j++];
            sum += n1 - i;
        }
    }
}

void merge_sort(int a[], int left, int right) {
    if(left + 1 < right) {
        int mid = (left + right) / 2;
        merge_sort(a, left, mid);
        merge_sort(a, mid, right);
        merge(a, left, mid, right);
    }
}

int main() {
    int n;
	cin >> n;
    int a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	merge_sort(a, 0, n);
    cout << sum << endl;

    return 0;
}