Merge Sort

Merge sort divides the array in half, sorts each of those halves, and then merges them back together. Each of those halves has the same sorting algorithm applied to it. Eventually, you are merging just two single-element arrays. It is the merge part that does all the heavy lifting.

The merge method operates by copying all the elements from the target array segment into a helper, keeping tack of where the start of the left and right halves should be (helperLeft and helperRight). We then iterate through helper, copy the smaller element from each half into the array. At the end, we copy any remaining elements into the target array.

Time Complexity: $O(N\times logN)$
Space Complexity: depends

C++ implementation

void merge(vector<int>& arr, int left, int mid, int right) {
	vector<int> v(right - left + 1);
	int i = left;
	int j = mid + 1;
	int k = left;
	while (i >= 0 && j >= 0) {
		if (arr[i] > arr[j]) {
			v[k++] = arr[i++];
		} else {
			v[k++] = arr[j++];
		}
	}
	while (i >= 0) {
		v[k++] = arr[i++];
	}
	
	while (j >= 0) {
		v[k++] = arr[j++];
	}
	for (int p = 0; p < static_cast<int>(v.size()), ++p) {
		arr[left + p] = v[p];
	}
}

void mergeSort(vector<int>& arr, int left, int right) {
	if (left >= right) return;
	int mid = left + (right - left) / 2;
	mergeSort(arr, left, mid);
	mergeSort(arr, mid + 1, right);
	merge(arr, left, mid, right);
}