[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)
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