Count Inversion Pairs with Merge Sort with C++

Input Description:

---

There are multiple test cases, and each test case begins with an integer n, indicating the number of elements in the sequence. After n, the next line includes the n distinct integers in the sequence.

Please note:

1. 1 <= n <= 1,000,000
2. The value of each number is within [1, 2^32-1]
3. It is also possible that the number of inversion pairs exceeds 2^32-1 but an unsigned long long variable will work fine.

---

I use merge sort to solve it. It pass five test cases, but in last test cases it Memory Limit Exceed. I don't know how can I solve this problem...

Online Judge Status

---

My code:

#include <iostream>
using namespace std;


unsigned long long _mergeSort(unsigned int arr[], unsigned int temp[], int left, int right);
unsigned long long merge(unsigned int arr[], unsigned int temp[], int left, int mid, int right);

/* This function sorts the input array and returns the
 number of inversions in the array */
unsigned long long mergeSort(unsigned int arr[], int array_size)
{
    unsigned int* temp = (unsigned int*)malloc(sizeof(unsigned int) * array_size);
    return _mergeSort(arr, temp, 0, array_size - 1);
}

/* An auxiliary recursive function that sorts the input array and
 returns the number of inversions in the array. */
unsigned long long _mergeSort(unsigned int arr[], unsigned int temp[], int left, int right)
{
    int mid;
    unsigned long long inv_count = 0;
    if (right > left) {
        /* Divide the array into two parts and call _mergeSortAndCountInv()
         for each of the parts */
        mid = (right + left) / 2;

        /* Inversion count will be sum of inversions in left-part, right-part
         and number of inversions in merging */
        inv_count = _mergeSort(arr, temp, left, mid);
        inv_count += _mergeSort(arr, temp, mid + 1, right);

        /*Merge the two parts*/
        inv_count += merge(arr, temp, left, mid + 1, right);
    }
    return inv_count;
}

/* This funt merges two sorted arrays and returns inversion count in
 the arrays.*/
unsigned long long merge(unsigned int arr[], unsigned int temp[], int left, int mid, int right)
{
    int i, j, k;
    unsigned long long inv_count = 0;

    i = left; /* i is index for left subarray*/
    j = mid; /* j is index for right subarray*/
    k = left; /* k is index for resultant merged subarray*/
    while ((i <= mid - 1) && (j <= right)) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        }
        else {
            temp[k++] = arr[j++];

            /*this is tricky -- see above explanation/diagram for merge()*/
            inv_count = inv_count + (mid - i);
        }
    }

    /* Copy the remaining elements of left subarray
     (if there are any) to temp*/
    while (i <= mid - 1)
        temp[k++] = arr[i++];

    /* Copy the remaining elements of right subarray
     (if there are any) to temp*/
    while (j <= right)
        temp[k++] = arr[j++];

    /*Copy back the merged elements to original array*/
    for (i = left; i <= right; i++)
        arr[i] = temp[i];

    return inv_count;
}

int main()
{
    int N;
    while(cin >> N)
    {
        unsigned int arr[N];
        for(int i=0; i<N; i++)
            cin >> arr[i];
        cout << mergeSort(arr, N) << endl;
    }

    return 0;
}