Merge Sort

MergeSort(A)
	if n = 1
		return A
	else
		Merge(MergeSort(A[1:n/2], A[n/2 + 1:n]))
		
Merge(A, B)
	l = A.length
	k = B.length
	if l = 0 return B
	if k = 0 = 0 return A
	if A[1] <= B[1]
		return A[1] concat merge(A[2:l], B[1:k])
	else:
		return y[1] concat merge(A[1:l], B[2:k])

Running Time

Running time of Merge - $O(k+l)$ Running time of MergeSort:

• $T(n)=2T(n/2)+O(n)$
• $a=2,b=2,d=1$
• 3rd case of Master Theorem $a=b^d$
• $T(n)=O(nlogn)$