10810 - Ultra-QuickSort

Print the no of inversions in each input. Since 'n' is large no of swaps required could be large, so make sure you are using 'unsigned long long' to store them. Though I have used them everywhere(I used find replace ;) ), but that is not required, elements can be stored in 'int'.

//
//  main.cpp
//  10810 - Ultra-QuickSort
//
//  Created by Panks on 06/06/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;


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

int main (int argc, const char * argv[])
{

    long long int t,tmp ;
    vector<long long int> store;
    cin>>t;
    while (t!=0) {
        store.clear();
        while (t--) {
            cin>>tmp;
            store.push_back(tmp);
        }
        cout<<mergeSort(&store[0], (int)store.size())<<endl;
        cin>>t;
        
    }
    
    return 0;
}







unsigned long long mergeSort(long long int arr[], long long int array_size)
{
    long long int *temp = (long long int *)malloc(sizeof(long long int)*array_size);
    return _mergeSort(arr, temp, 0, array_size - 1);
}

unsigned long long _mergeSort(long long int arr[], long long int temp[], long long int left, long long int right)
{
    long long int mid;
    unsigned long long inv_count = 0;
    if (right > left)
    {

        mid = (right + left)/2;

        inv_count  = _mergeSort(arr, temp, left, mid);
        inv_count += _mergeSort(arr, temp, mid+1, right);
        
        inv_count += merge(arr, temp, left, mid+1, right);
    }
    return inv_count;
}


unsigned long long int merge(long long int arr[], long long int temp[], long long int left, long long int mid, long long int right)
{
    long long int i, j, k;
    unsigned long long int inv_count = 0;
    
    i = left; /* i is index for left subarray*/
    j = mid;  /* i is index for right subarray*/
    k = left; /* i 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++];
            
            inv_count = inv_count + (mid - i);
        }
    }
    

    while (i <= mid - 1)
        temp[k++] = arr[i++];
    

    while (j <= right)
        temp[k++] = arr[j++];
    
    for (i=left; i <= right; i++)
        arr[i] = temp[i];
    
    return inv_count;
}