Merge Sort

Algorithm

proc merge-sort(A, p, r)
	if p < r then
		q = floor((p + r)/2)
		merge-sort(A, p, q)
		merge-sort(A, q+1, r)
		merge(A, (p,q), (q+1,r))

Merge comparisons

Assuming we have equal partitions with length m, the best is (consecutive partitions) is m and the worst (interleaved partitions) is 2m1.

Given different sized partitions ml the worst case comparisons is m+l1. When m is significantly less than l you can use binary search to improve performance.

Merge sort comparisons

We will only analyze the worst case. The recurrence is:

T(n)={0ifn=02T(n2)+(n1)otherwise

The closed-form is T(n)=nlgnn+1.