UVa 10327 - Flip Sort

// UVa 10327 - Flip Sort

#include <iostream>
#include <algorithm>
using namespace std;

#define datatype long long int

datatype a[1000], b[1000];

int merge(int ini, int mid, int fin) {
	for (int i = ini; i <= fin; i++)
		b[i] = a[i];
	int i = ini;
	int j = mid + 1;
	int k = ini;
	datatype count = 0;
	while (k <= fin) {
		if (i > mid)
			a[k++] = b[j++];
		else if (j > fin)
			a[k++] = b[i++];
		else if (b[i] <= b[j])
			a[k++] = b[i++];
		else {
			a[k++] = b[j++];
			count += mid - i + 1;
		}
	}
	return count;
}

datatype merge_sort(int ini, int fin) {
	if (ini == fin)
		return 0;
	else {
		int mid = (ini + fin) >> 1;
		datatype count = merge_sort(ini, mid) + merge_sort(mid + 1, fin);
		count += merge(ini, mid, fin);
		return count;
	}
}

int main() {
	int n;
	while (cin >> n) {
		for (int i = 0; i < n; i++)
			cin >> a[i];
		cout << "Minimum exchange operations : " << merge_sort(0, n - 1) << endl;
	}
	return 0;
}