#include <fstream>
#include <iostream>
#include <deque>
#include <ctime>

using namespace std;

void ReadArray( deque<int> & arr )
{
	ifstream arrfile("IntegerArray.txt");
	int a;
	while( arrfile >> a )
	{
		arr.push_back( a );
	}
}
unsigned long MergeSortInversions(
	const deque<int> & in,
	int from, int to,
	deque<int> & out
	)
{
	int diff = to - from;
	if( diff == 0 )
	{
		out.push_back( in[from] );
		return 0;
	}
	
	int div = (from + to) / 2;
	deque<int> aleft;
	unsigned long inv_left = MergeSortInversions( in, from, div, aleft );
	deque<int> aright;
	unsigned long inv_right = MergeSortInversions( in, div+1, to, aright );
	unsigned long invs = 0;
	while( aleft.size() != 0 && aright.size() != 0 )
	{
		int lval = *aleft.begin();
		int rval = *aright.begin();
		if( lval < rval )
		{
			out.push_back( lval );
			aleft.pop_front();
		}
		else
		{
			out.push_back( rval );
			aright.pop_front();
			invs += aleft.size();
		}
	}
	out.insert( out.end(), aright.begin(), aright.end() );
	out.insert( out.end(), aleft.begin(), aleft.end() );
	return inv_left + inv_right + invs;
}

unsigned long MergeSortInversions( const deque<int> & arr )
{
	deque<int> sorted;	
	unsigned long int invs = MergeSortInversions( arr, 0, arr.size()-1, sorted);
	return invs;
}

int main( /*int argc, char * argv[]*/ )
{
	deque<int> arr;
	ReadArray( arr );
	unsigned long int good_result = 2407905288U;
	cout <<  "Expected result: " << good_result << endl;
	cout << "Array of " << arr.size() << " elements." << endl;
	clock_t t = clock();
	unsigned long int merge_inv = MergeSortInversions( arr );
	t = clock() - t;
	cout << "Merge inv: " << merge_inv << endl;
	float ft = ((float)t)/CLOCKS_PER_SEC;
	cout << "Completed in " << t << " : " << ft << endl;
	return 0;
}