299 - Train Swapping

Just count the no. of inversion in array, using mergesort.

//
//  main.cpp
//  299 - Train Swapping
//
//  Created by Panks on 05/06/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
int mergeSort(int arr[], int array_size);
int  _mergeSort(int arr[], int temp[], int left, int right);
int merge(int arr[], int temp[], int left, int mid, int right);


int main (int argc, const char * argv[])
{
    int t,l,tmp,inv ;
    vector<int> store;
    cin>>t;
    while (t--) {
        inv=0;
        cin>>l;
        while (l--) {
            cin>>tmp;
            store.push_back(tmp);
        }
        inv=mergeSort(&store[0], (int)store.size());
        cout<<"Optimal train swapping takes "<<inv<<" swaps.\n";
        store.clear();
    }
    
    return 0;
}


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

int _mergeSort(int arr[], int temp[], int left, int right)
{
    int mid, 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;
}

int merge(int arr[], int temp[], int left, int mid, int right)
{
    int i, j, k;
    int inv_count = 0;
    
    i = left; 
    j = mid;  
    k = left; 
    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;
}