逆序对

算法导论题目： 设 A[0...N] 数组， 若 i < j 且 A[i] > A[j] 则称 (i, j) 为一个逆序对， 给出一个算法， 在最坏 O(nlgn) 的运行时间， 得到任意数组的逆序对个数。

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

int merge(int* intp, int a, int b, int c)
{
    int n = c - a;
    int* p = (int *) malloc(sizeof(int) * n);
    if (p == NULL) {
        printf("oom\n");
        exit(0);
    }

    memcpy(p, &intp[a], n * sizeof(int));
    int n1 = b - a;
    int n2 = n - n1;
    n = 0;

    int* p1 = p;
    int* p2 = p + n1;
    int ret = 0;

    while (n1 > 0 && n2 > 0) {
        if (*p1 >= *p2) {
            intp[n++] = *p2++;
            --n2;
        } else {
            intp[n++] = *p1++;
            --n1;
            ret += n2;
        }
    }

    if (n1 > 0) {
        memcpy(&intp[n], p1, n1 * sizeof(int));
    } else {
        memcpy(&intp[n], p2, n2 * sizeof(int));
    }

    free(p);
    return ret;
}

int merge_sort(int* intp, int len)
{
    int n = 0;
    if (len <= 1) {
        return 0;
    }
    int n1 = len / 2;
    
    n += merge_sort(intp, n1);
    n += merge_sort(&intp[n1], len - n1);
    n += merge(intp, 0, n1, len);
    return n;
}

void print(int* a, int len)
{
    for (int n = 0; n < len; ++n) {
        printf("%d ", a[n]);
    }
    printf("\n");
}

int main(int n, char** c)
{
    int a[] = {2, 3, 8, 6, 1};
    n = merge_sort(a, sizeof(a) / sizeof(a[0]));
    printf("result = %d\n", n);

    print(a, sizeof(a) / sizeof(a[0]));
    return 0;
}