mergesort to count inversions template for ACM/ICPC

mergesort.c

typedef int T;

inline bool less(T a, T b) {
	return a < b;
}

inline bool lessEq(T a, T b) {
	return a <= b;
}

int insert_sort(T ar[], int l, int r) {
	int count = 0;
	int i;
	for (i = l + 1; i < r; i++) {
		T t = ar[i];
		int j = i;
		while (j > l && less(t, ar[j-1])) {
			ar[j] = ar[j-1];
			j--;
			count++;
		}
		ar[j] = t;
	}
	return count;
}

long long merge(T ar[], T temp[], int l, int mid, int r) {
	long long count = 0;
	if (lessEq(ar[mid-1], ar[mid])) {
		return 0;
	}
	int len = mid - l;
	memcpy(temp, ar + l, len * sizeof(T));
	int i = 0;
	int j = mid;
	int k;
	for (k = l; k < r; k++) {
		if (i >= len) {
			ar[k] = ar[j++];
		} else if (j >= r) {
			ar[k] = temp[i++];
		} else if (less(ar[j], temp[i])) {
			ar[k] = ar[j++];
			count += len - i;
		} else {
			ar[k] = temp[i++];
		}
	}
	return count;
}

long long mergesort(T src[], T aux[], int l, int r) {
	if (r <= l + 1) {
		return 0;
	}
	if (r <= l + 8) {
		return insert_sort(src, l, r);
	}
	int mid = l + (r - l) / 2;
	long long count = 0;
	count += mergesort(src, aux, l, mid);
	count += mergesort(src, aux, mid, r);
	count += merge(src, aux, l, mid, r);
	return count;
}