Merge sort is a sorting algorithm that uses a divide-and-conquer approach to sort an array. The algorithm works by recursively dividing the array into two halves until each subarray contains only one element, then merging these subarrays back together in sorted order.

void mergeSort(vector<T>& arr) {
	mergeSortRecursive(arr, 0, arr.size() - 1);
}

void mergeSortRecursive(vector<T>& arr, int low, int high) {
	if (low >= high) return;
	
	int mid = (low + high) / 2;
	
	// Sort the left half
	mergeSortRecursive(arr, low, mid);
	
	// Sort the right half
	mergeSortRecursive(arr, mid + 1, high);
	
	// Merge the sorted halves
	merge(arr, low, mid, high);
}

void merge(vector<T>& arr, int low, int mid, int high) {
	vector<T> temp;
	
	int a = low,
	    b = mid + 1;
	    
	for (int k = low; k <= high; k++) {
		if (a <= mid && (b > high || arr[a] < arr[b])) {
			temp.push_back(arr[a++]);
			
			continue;
		}
		
		temp.push_back(arr[b++]);
	}
	
	for (int k = low; k <= high; k++) {
		arr[k] = temp[k - low];
	}
}

Analysis

Runtime Complexity

We can notice that at every recursion step the sub arrays are divided into two equally sized sub arrays each of length .

This means that for each level of recursion, the work performed on each totals where is the length of the array and is the cost to merge the elements of the array. Considering the array is split in half on each operation we can see that the number of levels of recursion is in the order of as the array is halved each iteration ().

When looking at the merge operation we can see we only iterate each element one time giving is a runtime of We can also consider the base cases where the work performed is where is the cost to process the base case, as we can see in the code example as we just return instantly after a single comparison.

Combining these facts we can determine runtime of our algorithm

Using big-O notation we can express this as follows