merge sort求逆序数

逆序数Submit: 1650   Accepted:255Time Limit: 2000MS  Memory Limit: 20000KDescription
给出一个序列，帮火星人求出该序列的逆序数。


Input
单组测试数据。
第一行为一个整数N，表示序列的长度，（1<= N < 2000000）。
接下来N行，每行一个整数Ai，表示该序列的第i个元素，其中 1<= Ai <= N。


Output
输出仅一行，为该序列的逆序数。


Sample Input

4
3
2
1
4


Sample Output

3



基于merge_sort的逆序数求解

#include <stdio.h>
#include <stdlib.h>

#define WORD sizeof(long)
#define MAX_INT 0x7fffffff

long long reverse;
long array[2000010];
long left[1000010];
long right[1000010];

merge(long *arr, long p, long q, long r)
{
    long i = 0, j = 0, total_len;
    long nleft = q - p + 1;
    long nright = r - q;

#if 0
    long *left = malloc(WORD * (nleft + 1));
    long *right = malloc(WORD * (nright + 1));
#endif
    for (i=0 ; i<nleft ; i++)
    {
        left[i] = arr[p + i];
    }
    left[i] = MAX_INT;
    for (i=0 ; i<nright ; i++)
    {
        right[i] = arr[q + 1 + i];
    }
    right[i] = MAX_INT;

    total_len = nleft + nright + p;
    i = j = 0;
    for (; p<total_len ;p++)
    {
        if (left[i] <= right[j])
        {
            arr[p] = left[i++];
        }
        else
        {
            arr[p] = right[j++];
            reverse += nleft - i; /*count reverse*/
        }
    }

#if 0
    free(left);
    free(right);
#endif
}

merge_sort(long *arr, long p, long r)
{
    if (p < r)
    {
        long q = (p + r) / 2;
        merge_sort(arr, p, q);
        merge_sort(arr, q + 1, r);
        merge(arr, p, q, r);
    }
}

int main(int argc, char *argv[])
{
    long N, i;
    scanf("%ld", &N);
    reverse = 0;
    for (i=0 ; i<N ; i++)
    {
        scanf("%ld", &array[i]);
    }
   
    merge_sort(array, 0, N - 1);

    printf("%lld\n", reverse);
}