{small lecturenumber - heblocknumber :} Merge Sort -- Recursive Sortingaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Mergingaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Merge Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Merge Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Merge Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Merge Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Merge Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Merge Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Merge Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Merge Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Merge Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Merge Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Merge Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Merge Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Merge Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Merge Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Divide & Conqueraddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Divide & Conqueraddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Quick Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Quick Sort - Partitioningaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Quick Sort - Partitioningaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Quick Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Quick Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Quick Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Quick Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Quick Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Quick Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Quick Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Quick Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Quick Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Quick Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Quick Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Quick Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Quick Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Quick Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Quick Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} {em Quick} Sort?addtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} {em Quick} Sort?addtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Quick Sort - Worst Caseaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Better Partitionsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Improving Quick Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Heap Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Heap Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Heap Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Heap Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Stabilityaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Stabilityaddtocounter {blocknumber}{1}Data Structures and AlgorithmsCS245-2014S-11Sorting in Θ(n lg n)David GallesDepartment of Computer ScienceUniversity of San Francisco11-0: Merge Sort – Recursive SortingBase Case:A list of length 1 or length 0 is already sortedRecursive Case:Split the list in halfRecursively sort two halvesMerge sorted halves togetherExample: 5 1 8 2 6 4 3 711-1: MergingMerge lists into a new temporary list, TMaintain three pointers (indices) i, j, and ni is index of left hand listj is index of right hand l istn is index of temporary list TIf A[i] < A[j]T [n] = A[i], increment n and ielseT [n] = A[j], increment n and jExample: 1 2 5 8 and 3 4 6 711-2: Θ() for Merge SortT (0) = c1for some constant c1T (1) = c2for some constant c2T (n) = nc3+ 2T (n/2) for some constant c3T (n) = nc3+ 2T (n/2)11-3: Θ() for Merge SortT (0) = c1for some constant c1T (1) = c2for some constant c2T (n) = nc3+ 2T (n/2) for some constant 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 constant c1T (1) = c2for some constant c2T (n) = nc3+ 2T (n/2) for some constant 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 constant c1T (1) = c2for some constant c2T (n) = nc3+ 2T (n/2) for some constant 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)11-6: Θ() for Merge SortT (0) = c1for some constant c1T (1) = c2for some constant c2T (n) = nc3+ 2T (n/2) for some constant 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 constant c1T (1) = c2for some constant c2T (n) = nc3+ 2T (n/2) for some constant 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