Merge Sort

The first programming challenge the course over at Coursera provided us with was to implement an algortihm for counting the inverions in an array. As it turns out, this can be achieved by applying a minor modification in the Merge Sort algorithm. I implemented it both in C++ and Python.
Python version

	def mergeSort(nums):
	if len(nums) < 2:
	return nums[:]
	a = nums[ 0 : len(nums)/2 ]
	b = nums[ len(nums)/2 : ]
	a = mergeSort(a)
	b = mergeSort(b)
	result = []
	i = 0
	j = 0
	for k in range(len(nums)):
	if i >= len(a):
	result.append(b[j])
	j += 1
	elif j >= len(b):
	result.append(a[i])
	i += 1
	else:
	if a[i] <= b[j]:
	result.append(a[i])
	i += 1
	else:
	result.append(b[j])
	j += 1
	return result

view raw mergesort.py hosted with ❤ by GitHub

C++ version

	template<typename T>
	std::vector<T> mergeSort(const std::vector<T>& nums)
	{
	if(nums.size() < 2)
	return nums;
	std::vector<T> a, b;
	a.assign(nums.begin(), nums.end() - nums.size()/2);
	b.assign(nums.end() - nums.size()/2, nums.end());
	a = mergeSort(a);
	b = mergeSort(b);
	std::vector<T> result;
	result.reserve(nums.size());
	for(int k = 0, j = 0, i = 0; k < nums.size(); k++)
	{
	if(i >= a.size())
	result.push_back(b[j++]);
	else if(j >= b.size())
	result.push_back(a[i++]);
	else
	{
	if(b[j] < a[i])
	result.push_back(b[j++]);
	else
	result.push_back(a[i++]);
	}
	}
	return result;
	}

view raw gistfile1.cpp hosted with ❤ by GitHub

I'll leave the method to calculate the inversions as an exercise for the reader, it's really not that difficult.