Mergesort

Mergesort is a recursive sorting algorithm. The core idea is that in each step, it sorts a sub-array by recursing from smaller sub-arrays half of its size, then merging them together.

It has a time complexity of $O(n\log n)$. Each recursive step takes $O(\log n)$ levels (because we halve the sort set), and processing each level takes $O(n)$ time.

Procedure

Mergesort operates on a subarray $[a,\cdots ,b]$ as follows:

• If $a=b$, then we don’t do anything, because the sub-array’s already sorted.
• Compute the position of the middle element: $k=\lfloor (a+b)/2\rfloor$.
• Recursively sort the subarray $[a,\cdots ,k]$, then the subarray $[k+1,\cdots ,b]$.
• Merge the sorted sub-arrays into a combined sorted sub-array $[a\cdots b]$.

Implementation

void mergeSort(vector<int>& nums, int begin, int end) {
	if (end <= begin) return;
 
	int k = (begin + end) / 2;
	mergeSort(nums, begin, k);
	mergeSort(nums, k + 1, end);
 
	// combine
	vector<int> temp(end - begin + 1);
	int write = 0;
	int first = begin, second = k + 1;
 
	while (first <= k and second <= end) {
		if (nums[first] <= nums[second]) {
			temp[write] = nums[first];
			first++;
		} else {
			temp[write] = nums[second];
			second++;
		}
		write++;
	}
	while (first <= k) temp[write++] = nums[first++];
	while (second <= end) temp[write++] = nums[second++];
 
	for (int i = 0; i < end - begin + 1; i++) nums[begin + i] = temp[i];
}