Merge Sort

#Sorting#Computer-Science#CS251 Merge sort is a recursive algorithm. It uses a divide and conquer strategy to split the array up and recombine it in a sorted order.

Pseudocode §

MergeSort(A: array, l: left index, r: right index)
	if (l < r)
		m <- (l+r)/2 // middle index
		MergeSort(A, l, m)
		MergeSort(A, m+1, r)
		Merge(A, l, m, r)
	end if
	return A
end MergeSort

Merge Sort is NOT in place

Runtime Analysis §

Merge() runs in $O(n)$ time

$T(n)=2T\left(\frac{n}{2}\right)+n$ $=2(2T(\frac{n}{4})+\frac{n}{2})+n$ $=2^2\cdot T\left(\frac{n}{4}\right)+2n$ $=2^3\cdot T\left(\frac{n}{8}\right)+3n$ $T(n)=2^k+T\left(\frac{n}{2^k}\right)+kn$ $T(1)=1$

$2^{{\log }_{2}n}\cdot T(1)+{\log }_2(n)\cdot n$ $=n+n\log n$ $\in \Theta (n\log n)$

Merge(A, l, m, r) $\in \Theta (n)$ §

Pseudocode §

Merge(A, l, m, r)
	n1 <- m - l + 1
	n2 <- r - m
	let L and R be array of sizes n1+1 and n2+1 respectively
	for (i = 0 to n1-1)
		L[i] <- A[l+i]
	endfor
	for (j=0 to n2-1)
		R[j] <- A[m+j+1]
	endfor
	L[n1] <- infinity, R[n2] <- infinity
	i=0, j=0
	for (k=l to r-1)
		if (L[i] <= R[j])
			A[k] <- L[i]
			i+=1
		else
			A[k] <- R[j]
			j+=1
		endif
	endfor
	return A
end Merge

Example of merging

Final Details of Merge Sort §

Merge sort $\in \Theta (n\log n)$ runtime

Is stable Is not in place Machine friendly (more so than Heap Sort)

• Linear access of memory compared to jumping around