MergeSort Review

This is a review about MergeSort by CLRS#3 & Algorithm#4.

Complexity

• Average
  $$
  T(n) = \Theta(n\lg{n})
  $$

<CLRS#3>

$$
T(n)=2T(n/2)+\Theta(n)
$$

Main Function

$$
T(n)=aT(n/b)+f(n)
$$

$$
1.\ T(n)=\Theta(n^{\log_b{a}}),\ if\ f(n)=n^{\log_{b}a - \varepsilon},\varepsilon>0.\
$$
$$
2.\ T(n)=\Theta(n\lg{n}),\ if\ f(n)=n^{\log_{b}a}.\
$$
$$
3.\ T(n)=\Theta(f(n)),\ if\ f(n)=n^{\log_{b}a + \varepsilon},\varepsilon>0.
$$

<Algorithm#4>

MergeSort

merge(A,lo,mid,hi):
	copy B by A from lo to hi
	i = lo
	j = mid+1
	for k = lo to hi
		if i>mid
			A[k] = B[j++]
		elif j>hi
			A[k] = B[i++]
		elif B[j]<B[i]
			A[k] = B[j++]
		else
			A[k] = B[i++]

sort(A,lo,hi):
	if lo>=hi
		return
	mid = lo + (hi-lo)/2
	sort(A,lo,mid)
	sort(A,mid+1,hi)
	merge(A,lo,mid,hi)
	
sort(A,1,A.length)

MergeSortBU

sortBU(A):
	for sz = 1 to N //sub-array size
		for	i = 1 to N-sz //sub array start
			merge(A,i,i+sz-1,Math.min(N,i+sz+sz-1))
			i = i + sz + sz //next sub array start
		sz = sz + sz + sz //expand sub-array size