Sorting
1. Split pile in half
2. Sort each half (possibly recursively with merge sort)
3. Recombine lists
Merge sort
Merge sort
Merge sort
Merge sort
Merge sort
Merge sort
Merge sort
Merge sort
Merge sort
Merge sort
Merge(L[1, …, nl], R[1, …, nr]
i=1, j=1, k=1
while i < nl OR j < nr
if L[i] < R[j]
A[k] = L[i], i=i+1
else
A[k] = R[j], j=j+1
k = k+1
Merge sort
Sort: {4, 5, 3, 8, 1, 6, 2}
Merge sort
Sort: {4, 5, 3, 8, 1, 6, 2} - Split {4, 5, 3}{8, 1, 6, 2} - Split
{4, 5}{3}{8,1}{6,2} – Split {4}{5}{3}{8}{1}{6}{2} – Merge {4, 5}{3} {1, 8} {2, 6} – Merge {3, 4, 5} {1, 2, 6, 8} – Merge
{1, 2, 3, 4, 5, 6, 8}
Merge sort
Corectness:
Base: A[] empty (sorted), at L&R[1] Step: In the while loop, the smallest element in L[] or R[] will be added and is larger than all already in A[] Termination: while loop end after all elements in L[] and R[] have been added to A[]
Merge sort
Run time: T(n) =
Merge sort
Run time: (recurrence relation) T(n) = {O(1) if n=1, otherwise...
Divide + 2T(n/2) + Merge}
T(n) = {O(1) if n=1, otherwise... O(1) + 2T(n/2) + O(n)}
T(n) = O(n lg n)
Merge sort
Master's theorem: (proof 4.6)
For a > 1, b > 1,T(n) = a T(n/b) + f(n)
If f(n) is… (3 cases)
1. O(nc) for c
Divide & conquer
If you have something of the form: T(n) = a T(n/b) + f(n)
acts like
Case 1: nlogb a grows “significantly” faster, then overall growth just nlogb a
Case 2: Both grow same, tack on lg n: nlogb a lg(n)
Case 3: f(n) grows “significantly” faster, then overall growth just f(n)
Master’s theorem: TL;DR
What are the running times of… (1) T(n) = 4T(n/2) + n2
(2) T(n) = 4T(n/4) + n2 (3) T(n) = 8T(n/2) + n2
Master’s theorem
What are the running times of… (1) T(n) = 4T(n/2) + n2
O(n2 lg(n))
(2) T(n) = 4T(n/4) + n2
O(n2)
(3) T(n) = 8T(n/2) + n2
O(n3)
Master’s theorem
Important note on “significantly”: must grow a power larger
n2 vs. n3 = “significant”
n2 vs. n2.0000001 = “significant”
n2 vs. n2 lg(n) = NOT “significant”
Master’s theorem
Which works better for multi-cores: insertion sort or merge sort?
Why?
Divide & conquer
Which works better for multi-cores: insertion sort or merge sort?
Why?
Merge sort! After the problem is split, each core and individually sort a sub-list and only merging needs to be done synchronized
Divide & conquer