[InversionPair]
inversionPair只需要在merge函数中增加3行代码记录即可。先将inversion_pairs初始化为0，当L[i]>R[j]时，更新inversion_pairs=inversion_pairs+(n1-i),最后返回即可。同时在merge_sort中返回left_pair，right_pair和corss_pair之和即可。
C++ Code
/*
version: 1.0
author: hellogiser
blog: http://www.cnblogs.com/hellogiser
date: 2014/6/25
*/
int merge_pair(int *A, int p, int q, int r)
{
//Li: p...q Rj: q+1...r
int n1 = q - p + 1;
int n2 = r - (q + 1) + 1;
int *L = new int[n1 + 1];
int *R = new int[n2 + 1];
// copy L and R
for (int i = 0; i < n1; i++)
L[i] = A[p + i];
for (int j = 0; j < n2; j++)
R[i] = A[q + 1 + j];
// mark end
L[n1] = INT_MAX;
R[n2] = INT_MAX;
int i = 0; // left
int j = 0; // right
int k = 0; // whole
//============================
int inversion_pairs = 0;
//============================
for (k = p; k <= r; k++)
{
if (L[i] <= R[j])
{
A[k] = L[i];
i++;
}
else
{
// L[i]>R[j]
A[k] = R[j];
j++;
//============================
inversion_pairs += (n1 - i);
//============================
}
}
delete []L;
delete []R;
//============================
return inversion_pairs;
//============================
}
int inversion_pair(int *A, int p, int r)
{
if (p < r)
{
int q = (p + r) / 2;
//======================================
int left_pair = inversion_pair(A, p, q);
int right_pair = inversion_pair(A, q + 1, r);
int cross_pair = merge_pair(A, p, q, r);
return left_pair + right_pair + cross_pair;
//======================================
}
else
return 0;
}
int InversionPair(int *A, int n)
{
return inversion_pair(A, 0, n - 1);
}