[SOLVED] CS Sorting

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 < nrif L[i] < R[j]A[k] = L[i], i=i+1elseA[k] = R[j], j=j+1k = k+1 Merge sortSort: {4, 5, 3, 8, 1, 6, 2} Merge sortSort: {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 sortCorectness: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 sortRun time: T(n) = Merge sortRun 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 sortMaster’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 log a, T(n) is (f(n)) b
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)
Masters 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
Masters 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)
Masters 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
Masters 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