CS245-2014S-11 Sorting in Θ(n lg n) 111-0: Merge Sort – Recursive Sorting• Base Case:• A list of length 1 or length 0 is already sorted• Recursive Case:• Split the list in half• Recursively sort two halves• Merge sorted halves togetherExample: 5 1 8 2 6 4 3 7 11-1: Merging• Merge lists into a new temporary list, T• Maintain three pointers (indices) i, j, and n• i is index of left hand list• j is index of right hand list• n is index of temporary list T• If A[i] < A[j]• T [n] = A[i], increment n and i• else• T [n] = A[j], increme nt n and jExample: 1 2 5 8 and 3 4 6 711-2: Θ() for Merge SortT (0) = c1for some constan t c1T (1) = c2for some constan t c2T (n) = nc3+ 2T (n/2) for some constan t c3T (n) = nc3+ 2T (n/2)11-3: Θ() for Merge SortT (0) = c1for some constan t c1T (1) = c2for some constan t c2T (n) = nc3+ 2T (n/2) for some constan t c3T (n) = nc3+ 2T (n/2)= nc3+ 2(n/2c3+ 2T (n/4))= 2nc3+ 4T (n/4)11-4: Θ() for Merge SortT (0) = c1for some constan t c1T (1) = c2for some constan t c2T (n) = nc3+ 2T (n/2) for some constan t c3T (n) = nc3+ 2T (n/2)= nc3+ 2(n/2c3+ 2T (n/4))= 2nc3+ 4T (n/4)= 2nc3+ 4(n/4c3+ 2T (n/8))= 3nc3+ 8T (n/8))11-5: Θ() for Merge SortT (0) = c1for some constan t c1T (1) = c2for some constan t c2T (n) = nc3+ 2T (n/2) for some constan t c3CS245-2014S-11 Sorting in Θ(n lg n) 2T (n) = nc3+ 2T (n/2)= nc3+ 2(n/2c3+ 2T (n/4))= 2nc3+ 4T (n/4)= 2nc3+ 4(n/4c3+ 2T (n/8))= 3nc3+ 8T (n/8))= 3nc3+ 8(n/8c3+ 2T (n/16))= 4nc3+ 16T (n/16)11-6: Θ() for Merge SortT (0) = c1for some constan t c1T (1) = c2for some constan t c2T (n) = nc3+ 2T (n/2) for some constan t c3T (n) = nc3+ 2T (n/2)= nc3+ 2(n/2c3+ 2T (n/4))= 2nc3+ 4T (n/4)= 2nc3+ 4(n/4c3+ 2T (n/8))= 3nc3+ 8T (n/8))= 3nc3+ 8(n/8c3+ 2T (n/16))= 4nc3+ 16T (n/16)= 5nc3+ 32T (n/32)11-7: Θ() for Merge SortT (0) = c1for some constan t c1T (1) = c2for some constan t c2T (n) = nc3+ 2T (n/2) for some constan t c3T (n) = nc3+ 2T (n/2)= nc3+ 2(n/2c3+ 2T (n/4))= 2nc3+ 4T (n/4)= 2nc3+ 4(n/4c3+ 2T (n/8))= 3nc3+ 8T (n/8))= 3nc3+ 8(n/8c3+ 2T (n/16))= 4nc3+ 16T (n/16)= 5nc3+ 32T (n/32)= knc3+ 2kT (n/2k)11-8: Θ() for Merge SortT (0) = c1T (1) = c2T (n) = knc3+ 2kT (n/2k)Pick a value for k such that n/2k= 1:n/2k= 1n = 2klg n = kT (n) = (lg n)nc3+ 2lg nT (n/2lg n)= c3n lg n + nT (n/n)= c3n lg n + nT (1)= c3n lg n + c2n∈ O(n lg n)11-9: Θ() for Merge SortT(n)11-10: Θ() for Merge SortCS245-2014S-11 Sorting in Θ(n lg n) 3c*nT(n/2) T(n/2)11-11: Θ() for Merge Sortc*nc*(n/2) c*(n/2)T(n/4) T(n/4) T(n/4) T(n/4)11-12: Θ() for Merge Sortc*nc*(n/2) c*(n/2)c*(n/4) c*(n/4) c*(n/4) c*(n/4)c*nc*nc*nc*n......... ...11-13: Θ() for Merge Sortc*nc*(n/2) c*(n/2)c*(n/4) c*(n/4) c*(n/4) c*(n/4)c*nc*nc*nc*nlg nlevels......... ...11-14: Θ() for Merge SortCS245-2014S-11 Sorting in Θ(n lg n) 4c*nc*(n/2) c*(n/2)c*(n/4) c*(n/4) c*(n/4) c*(n/4)c*nc*nc*nc*nlg nlevels......... ...c*n lg nTotal time =Θ(n lg n)11-15: Θ() for Merge SortT (0) = c1for some constant c1T (1) = c2for some constant c2T (n) = nc3+ 2T (n/2) for some constan t c3T (n) = aT (n/b) + f(n)a = 2, b = 2, f(n) = nnlogba= nlog22= n ∈ Θ(n)By second case of the Master Method, T (n) ∈ Θ(n lg n)11-16: Divide & ConquerMerge Sort:• Divide the list two parts• No work required – just calculate midpoint• Recursively sort two parts• Combine sorted lists into one list• Some work required – need to merge lists11-17: Divide & ConquerQuick Sort:• Divide the list two parts• Some work required – Small elements in left sublist, large elements in right sublist• Recursively sort two parts• Combine sorted lists into one list• No work required !11-18: Quick Sort• Pick a pivot elementCS245-2014S-11 Sorting in Θ(n lg n) 5• Reorder the list:• All elements < pivot• Pivot element• All elements > pivot• Recursively sort elements < pivot• Recursively sort elements > pivotExample: 3 7 2 8 1 4 611-19: Quick Sort - PartitioningBasic Idea:• Swap pivot elememt out of the way (we’ll swap it bac k later)• Maintain two pointers, i and j• i points to the beginning of the list• j points to the end of the list• Move i and j in to the middle of the list – ensuring that all elements to the left of i are < the pivot, and allelememnts to the right of j are gre ater than th e p ivot• Swap pivot element back to middle of list11-20: Quick Sort - PartitioningPseudocode:• Pick a pivot index• Swap A[pivotindex] and A[high]• Set i ← low, j ← h igh−1• while (i <= j)• while A[i] < A[pivot], increment i• while A[j] > A[pivot], decrement i• swap A[i] and A[j]• increment i, decrem ent j• swap A[i] and A[pivot]11-21: Θ() for Quick Sort• Coming up with a recurrence relation for quicksort is harder th a n mergesort• How the problem is divided depends upon the dataCS245-2014S-11 Sorting in Θ(n lg n) 6• Break list into:size 0, size n − 1size 1, size n − 2. . .size ⌊(n − 1)/2⌋, size ⌈(n − 1)/2⌉. . .size n − 2, size 1size n − 1, size 011-22: Θ() for Quick SortWorst case performance occurs wh en break list into size n − 1 and size 0T (0) = c1for some constant c1T (1) = c2for some constant c2T (n) = nc3+ T (n − 1) + T (0) f or som e constant c3T (n) = nc3+ T (n − 1) + T (0)= T (n − 1) + nc3+ c211-23: Θ() for Quick Sort Worst case: T (n) = T (n − 1) + nc3+ c2T (n)= T (n − 1) + nc3+ c211-24: Θ() for Quick Sort Worst case: T (n) = T (n − 1) + nc3+ c2T (n)= T (n − 1) + nc3+ c2= [T (n − 2) + (n − 1)c3+ c2] + nc3+ c2= T (n − 2) + (n + (n − 1))c3+ 2c211-25: Θ() for Quick Sort Worst case: T (n) = T (n − 1) + nc3+ c2T (n)= T (n − 1) + nc3+ c2= [T (n − 2) + (n − 1)c3+ c2] + nc3+ c2= T (n − 2) + (n + (n − 1))c3+ 2c2= [T (n − 3) + (n − 2)c3+ c2] + (n + (n − 1))c3+ 2c2= T (n − 3) + (n + (n − 1) + (n − 2))c3+ 3c211-26: Θ() for Quick Sort Worst case: T (n) = T (n − 1) + nc3+ c2T (n)= T (n − 1) + nc3+ c2= [T (n − 2) + (n − 1)c3+ c2] + nc3+ c2= T (n − 2) + (n + (n − 1))c3+ 2c2= [T (n − 3) + (n − 2)c3+ c2] + (n + (n − 1))c3+ 2c2= T (n − 3) + (n + (n − 1) + (n − 2))c3+ 3c2= …