# Merge Sort (122A)

Given A[1...n]: List<number>, the idea of merge sort is:

function MergeSort(A[1...n]):
	sorted_left = sort left half      // Recursion Magic
	sorted_right = sort right half    // Recursion Magic
	merge(sorted_left, sorted_right)

We need to split the array in half. Let low and high denote the current starting and ending indices of the array (inclusive). Then we can find the middle index mid by:

mid = floor((low + high) / 2)

Note that this could cause integer overflow when low and high are large. A better way would be:

mid = floor(low + ((high - low) / 2))

And the recursive calls are:

MergeSort(A[1...mid])
MergeSort(A[mid + 1...high])

This is where we actually do the comparison. We have 2 base cases:

1. The array is empty or has 1 element, then we do nothing.

   if A is empty:
       return

2. The array has exactly 2 elements, then we directly compare.
   • This case could be implicitly handled by merging two 1–element arrays, so no need to explicitly implement this case.

Now that the recursion has sorted the left and right array for us, we need to merge them together. We can use the 2 pointer approach here.

Let l and r be the traversing pointers in the left & right sorted arrays respectively.

It’s probably easier to consider merging with 2 separate arrays first.

function Merge2SortedArrays(L[1...n], R[1...m]) -> List<number>:
	l = 0  // traverses L array
	r = 0  // traverses R array
	output = []

	while neither pointer has reached the end:
		if L[l] should come before R[r]: // call the predicate here
			push L[l] into output
			l++
		else:
			push R[r] into output
			r++

	remaining_elements = L if l not at the end, R if r not at the end
	push all of remaining_elements into output

	return output

Translate into expressions: (Assuming we are sorting in ascending order. Flip < to > if reversed.)

function Merge2SortedArrays(L[1...n], R[1...m]) -> List<number>:
	l = 0
	r = 0
	output = []

	while l != n and r != m:
		if L[l] < R[r]:
			push L[l] into output
			l++
		else:
			push R[r] into output
			r++

	while l != n:
		push L[l] into output
		l++

	while r != m:
		push R[r] into output
		r++

	return output

The 2nd and 3rd while loops are safe because at most 1 of them will run, and the loop that runs corresponds to the array that has all its remaining elements \geqslant the last element in output.

We can also see that this is a linear scan, so the runtime is O(n).

In actual implementation, don’t actually slice the main array into L and R because passing arrays on the stack is expensive. Instead, pass in an extra parameter mid to indicate where the left half ends, then merge with the same 2 pointer approach.

At the end, instead of returning output, replace all elements in the parameter array with output. This requires the main array to be passed as a reference so it may be different depending on the language.

//pseudocode
function MergeSort(A[1...n]):
	if n > 1:
		mid = floor(n / 2)
		MergeSort(A[1...mid])
		MergeSort(A[mid + 1...n])
		Merge(A, mid)