编辑代码

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

int merge(int *array, int arrStart, int arrMiddle, int arrEnd) {
    int arrLen = arrEnd - arrStart;
    if (arrLen < 2) return 0;

    int *temp = (int *) malloc(arrLen * sizeof(int));
    int i = arrStart;
    int j = arrMiddle;
    int tempIndex = 0;
	int count = 0;

    while (i<arrMiddle && j<arrEnd)
        if (array[i] > array[j]) {
            temp[tempIndex++] = array[j++];
            count += (arrMiddle-i);
        }
        else temp[tempIndex++] = array[i++];
    while (i < arrMiddle) temp[tempIndex++] = array[i++];
    while (j < arrEnd) temp[tempIndex++] = array[j++];
    for ((tempIndex=0, i=arrStart); (tempIndex<arrLen && i<arrEnd); (++tempIndex, ++i))
        array[i] = temp[tempIndex];
    free(temp);
    temp = NULL;

    return count;
}

int mergeSort(int *array, int arrStart, int arrEnd) {
    int arrLen = arrEnd - arrStart;
    if (arrLen < 0) return 0;
    if (arrLen <= 1) return 0;

	int count = 0;
    int middle = arrStart + floor(arrLen / 2);

    count += mergeSort(array, arrStart, middle);
    count += mergeSort(array, middle, arrEnd);
    
    return count + merge(array, arrStart, middle, arrEnd);
}

void test(int *array, int length) {
	int i, count;
	for (i=0; i<length; i++) printf("%d ", array[i]);
	printf("\n");
	count = mergeSort(array, 0, length);
	for (i=0; i<length; i++) printf("%d ", array[i]);
	printf("\n%d\n", count);
}

int main() {
    int array0[] = {3, 1, 4, 1, 5, 9};
    test(array0, sizeof(array0)/sizeof(int));
    int array1[] = {4, 3, 2, 1};
    test(array1, sizeof(array1)/sizeof(int));
    int array2[] = {0};
    test(array2, sizeof(array2)/sizeof(int));
    int array3[] = {};
    test(array3, sizeof(array3)/sizeof(int));
    int array4[] = {1, 2, 3, 4};
    test(array4, sizeof(array4)/sizeof(int));
	return 0;
}