Merge Sort: Trading Space for Time

The sorting algorithms that we have reviewed so far - selection, insertion, shell - had constant space complexity, meaning they used a fixed amount of memory that was not dependent on the size of the input. The algorithm we consider in this post, the merge sort, reaches the limit of efficiency but at the cost of additional space.

The merge sort proceeds by using the divide and conquer method. Namely, it splits a list into two sub-lists, recursively down to the base case of 1, and sorts each half. On the way back up the recursion, it merges the halves together again. The merge itself simply picks the lowest number from each half to put in place until entries are exhausted (and so on).

The recursive sort method, in the form of a local lambda, looks like this.

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
};

Provided a given low and high index, we first calculate the mid index, which marks the middle of the current list. We then sort the left and right halves of the current list, and then combine the halves. The combine function is where the magic happens.

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++];
		}
	}
};

Using two pointers to represent each half, left and right, we store the unsorted values for each half in the temporary aux array and then overwrite the original list with sorted values, picking the lowest value from both halves as we go until we have reached the end of both halves. Thus, by the time we reach the top of the recursion, the full list will have been sorted. To begin the recursion, we call the sort method for the full list.

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

This algorithm achieves linearithmic complexity (O(nlogn)), which represents optimal efficiency for sorting algorithms. However, the tradeoff is that we must maintain the aux list, which takes space proportional to the size of the input. Thus, the merge sort may not be the best choice for memory-bound applications.