merge-sort.h

#include <vector>

template<typename T>
void exchange(vector<T>& list, int i, int j)
{
	T temp = list[i];
	list[i] = list[j];
	list[j] = temp;
}

/**
 * The merge sort proceeds using the divide
 * and conquer method. Namely, it recursively
 * splits a list down to the base case of 1
 * and sorts each sub-list, merging those lists
 * together on the way back up the recursion.
 * The merge itself simply picks the lowest
 * number from the dual lists to put in place
 * until entries are exhausted (and so on).
 * It achieves linearithmic complexity (O(nlogn))
 * but at the cost of n space to hold
 * temporary results.
 */
template<typename T>
void merge_sort(vector<T>& list)
{
	vector<T> aux;
	aux.resize(list.size());

	auto combine = [&list, &aux](int low, int mid, int high)
	{
		// populate aux with relevant elements
		for (int i = low; i <= high; ++i)
		{
			aux[i] = list[i];
		}

		// set pointers for left and right lists 
		int left = low;
		int right = mid + 1;

		// go across range, picking least as we go
		for (int i = low; i <= high; ++i)
		{
			if (left > mid) // ran out of left
			{
				list[i] = aux[right++];
			}

			else if (right > high) // ran out of right
			{
				list[i] = aux[left++];
			}

			else if (aux[right] < aux[left]) // right smaller
			{
				list[i] = aux[right++];
			}

			else // left smaller
			{
				list[i] = aux[left++];
			}
		}
	};

	std::function<void(int, int)> sort = [&combine, &sort](int low, int high)
	{
		if (high <= low) // base case
		{
			return;
		}

		int mid = low + (high - low) / 2;
		sort(low, mid); // sort left half
		sort(mid + 1, high); // sort right half
		combine(low, mid, high); // combine both halves
	};

	sort(0, (int)list.size() - 1);
}