This doc has been marked needs-review. Following information are in upcoming update plan.

mooyyu

O2 - 并归排序

c++11 sort functional 

int ar[maxn];

template< class type, class Comp >
void merge_sort(type *v, int l, int r, Comp cmp) {
	static int i, j, pos;
	static type bak[maxn];
	if (l >= r - 1) return ;
	const int mid = (l + r) >> 1u;
	msort(v, l, mid, cmp);
	msort(v, mid, r, cmp);
	i = l, j = mid, pos = l;
	while (i < mid && j < r) {
		if (cmp(v[i], v[j])) bak[pos++] = v[i++];
		else bak[pos++] = v[j++];
	}
	while (i < mid) bak[pos++] = v[i++];
	while (j < r) bak[pos++] = v[j++];
	while (--pos >= l) v[pos] = bak[pos];
}

Usage

如果不是自定义比较函数, 一般cmp只能是less_equal<>()和greater_equal<>().

并归排序的运用

计算逆序对的数量 
typedef unsigned long long ullong;

int ar[maxn];

template< class type, class Comp >
ullong cpa(type *v, int l, int r, Comp cmp) {
	static int i, j, pos;
	static type bak[maxn];
	if (l >= r - 1) return 0;
	const int mid = (l + r) >> 1u;
	ullong ret = 0;
	ret += cpa(v, l, mid, cmp);
	ret += cpa(v, mid, r, cmp);
	i = l, j = mid, pos = l;
	while (i < mid && j < r) {
		if (cmp(v[i], v[j])) bak[pos++] = v[i++];
		else bak[pos++] = v[j++], ret += mid - i;
	}
	while (i < mid) bak[pos++] = v[i++];
	while (j < r) bak[pos++] = v[j++];
	while (--pos >= l) v[pos] = bak[pos];
	return ret;
}

计算正序对的数量同理.