Merge Sort

We need to sort a list of numbers in ascending order. Not all algorithms are limited to swapping consecutive elements. One algorithm is merge sort which is based on recursion.

Merge sort works as follows…

• If a = b, do not do anything because the subarray is already sorted
• Calculate the position of the middle element (similar to how its done in binary search)
• Recursively sort the subarray array[a...k
• Recursively sort the subarray array[k+1...b
• Merge the sorted subarrays into a sorted subarray

This algorithm is efficient since you half the subarray size at each steps which makes this algorithm $O\left(n\log n\right)$ since the halving step makes it $\log n$ and processing each level takes $O\left(n\right)$ time.

function mergeSort(a[1...n])
Input: An array of n numbers a[1...n]
Output: A sorted version of this array

if n > 1:
	return merge(mergesort(a[1...floor(n/2)]), mergesort(a[floor(n/2)+1...n]))
else:
	return a

Merge works by taking two sorted arrays and building a new array element by element taking the smaller element of the front of both arrays.

function merge(x[1...k],y[1...l])
if k = 0:
	return y[1...l]
if l = 0:
	return x[1...k]
if x[1] <= y[1]:
	return x[1] cat merge(x[2...k],y[1...l])
else:
	return y[1] cat merge(x[1...k],y[2...l])

The runtime of this is $O(k+l)$.

The recurrence relationship of merge sort can be written as $T(n)=2T\left(\lfloor \frac{n}{2}\rfloor \right)+O(n)=O(n\log n)$