ALDS1_5_B マージソートをC++で解いてみた[AIZU ONLINE JUDGE]

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

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

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

問題文
解答
感想
まとめ

問題文

マージソート（Merge Sort）は分割統治法に基づく高速なアルゴリズムで、次のように実装することができます。
（マージソートのアルゴリズムについては以下のリンクに書かれています）
n 個の整数を含む数列 S を上の疑似コードに従ったマージソートで昇順に整列するプログラムを作成してください。また、mergeにおける比較回数の総数を報告してください。
入力
１行目に n、２行目に S を表す n 個の整数が与えられます。
出力
１行目に整列済みの数列 S を出力してください。数列の隣り合う要素は１つの空白で区切ってください。２行目に比較回数を出力してください。
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_B

解答

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

int ans = 0;

void merge(int A[], int left, int mid, int right);

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);
    }
}

void merge(int A[], int left, int mid, int right) {
    int n1 = mid - left, n2 = right - mid;
    int L[n1], R[n2];

    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] = INT_MAX;
    R[n2] = INT_MAX;

    for(int i = 0, j = 0, k = left; k < right; k++) {
        if(L[i] <= R[j]) {
            A[k] = L[i++];
            ans++;
        } else {
            A[k] = R[j++];
            ans++;
        }
    }
}

int main() {
    int n;
	cin >> n;
    int S[n];
	for (int i = 0; i < n; i++) {
		cin >> S[i];
	}

    merge_sort(S, 0, n);

    for(int i = 0; i < n - 1; i++) {
        cout << S[i] << " ";
    }
    cout << S[n - 1] << endl;
    cout << ans << endl;

    return 0;
}