MergeSort Algorithm - CIS 3490 PDF

MergeSort CIS 3490 Joe Sawada and Daniel Gabrić University of Guelph CIS 3490 1/7 Divide and Conquer (1) Divide a computational problem into one or more subproblems of smaller size (2) Recursively solve...

MergeSort CIS 3490 Joe Sawada and Daniel Gabrić University of Guelph CIS 3490 1/7 Divide and Conquer (1) Divide a computational problem into one or more subproblems of smaller size (2) Recursively solve each subproblem (3) Conquer by merging the solutions to the subproblems to solve the original problem Important: Be careful to handle the base cases CIS 3490 2/7 Divide and Conquer (1) Divide a computational problem into one or more subproblems of smaller size (2) Recursively solve each subproblem (3) Conquer by merging the solutions to the subproblems to solve the original problem Important: Be careful to handle the base cases Application to sorting: CIS 3490 2/7 Merge Sort MergeSort: Sort a list S = s1 , s2 ,... , sn , by divide and conquer: (1) Divide the list into two lists of size (about) n/2 CIS 3490 3/7 Merge Sort MergeSort: Sort a list S = s1 , s2 ,... , sn , by divide and conquer: (1) Divide the list into two lists of size (about) n/2 (2) Recursively sort the two sub-lists CIS 3490 3/7 Merge Sort MergeSort: Sort a list S = s1 , s2 ,... , sn , by divide and conquer: (1) Divide the list into two lists of size (about) n/2 (2) Recursively sort the two sub-lists (3) Conquer by merging the two sorted lists into one sorted list by repeatedly removing the smallest element from the two lists (which must be at the front of one of the two lists) and appending to the end of the new list CIS 3490 3/7 Merge Sort MergeSort: Sort a list S = s1 , s2 ,... , sn , by divide and conquer: (1) Divide the list into two lists of size (about) n/2 (2) Recursively sort the two sub-lists (3) Conquer by merging the two sorted lists into one sorted list by repeatedly removing the smallest element from the two lists (which must be at the front of one of the two lists) and appending to the end of the new list 1: function MergeSort( S ) 2: if n = 1 then return s1. base case 3: S1 ← s1 , s2 ,... , sbn/2c. first half of S 4: S2 ← sbn/2c+1 ,... , sn−1 , sn. second half of S 5: return Merge( MergeSort(S1 ), MergeSort(S2 ) ) CIS 3490 3/7 Merge Merge sorted lists S1 = a1 , a2 ,... , an and S2 = b1 , b2 ,... , bm into sorted list L 1: function Merge( S1 , S2 ) 2: i ← 1; j←1 3: while (i ≤ n and j ≤ m) do. merge S1 and S2 until one is empty 4: if ai ≤ bj then 5: Li+j−1 ← ai 6: i←i+1 7: else 8: Li+j−1 ← bj 9: j ←j+1 10: while i ≤ n do. empty S1 11: Li+j−1 ← ai 12: i←i+1 13: while j ≤ m do. empty S2 14: Li+j−1 ← bj 15: j ←j+1 16: return L CIS 3490 4/7 Analyzing MergeSort Theorem Merge(S1 , S2 ) runs in O(n) time, where n = |S1 | + |S2 |. What is the running time of MergeSort? - We generally analyze recursive algorithms using recurrence equations. I T (n): the running time of the algorithm where n is the number of elements in the initial list. Assuming that n is a power of 2: T (n) = 2T (n/2) + O(n) since there are two recursive calls of size n/2, and the Merge routine requires O(n) time. CIS 3490 5/7 Analyzing MergeSort Theorem Merge(S1 , S2 ) runs in O(n) time, where n = |S1 | + |S2 |. What is the running time of MergeSort? - We generally analyze recursive algorithms using recurrence equations. I T (n): the running time of the algorithm where n is the number of elements in the initial list. Assuming that n is a power of 2: T (n) = 2T (n/2) + O(n) since there are two recursive calls of size n/2, and the Merge routine requires O(n) time. Is this enough? CIS 3490 5/7 Analyzing MergeSort Theorem Merge(S1 , S2 ) runs in O(n) time, where n = |S1 | + |S2 |. What is the running time of MergeSort? - We generally analyze recursive algorithms using recurrence equations. I T (n): the running time of the algorithm where n is the number of elements in the initial list. Assuming that n is a power of 2: T (n) = 2T (n/2) + O(n) since there are two recursive calls of size n/2, and the Merge routine requires O(n) time. Is this enough? No, we need to establish a base case: T (1) = O(1) CIS 3490 5/7 Analyzing MergeSort Theorem Merge(S1 , S2 ) runs in O(n) time, where n = |S1 | + |S2 |. What is the running time of MergeSort? - We generally analyze recursive algorithms using recurrence equations. I T (n): the running time of the algorithm where n is the number of elements in the initial list. Assuming that n is a power of 2: T (n) = 2T (n/2) + O(n) since there are two recursive calls of size n/2, and the Merge routine requires O(n) time. Is this enough? No, we need to establish a base case: T (1) = O(1) It is often easier to replace the big-Oh notation with actual constants that bound the running time:  b if n = 1 T (n) = 2T (n/2) + cn if n > 1 CIS 3490 5/7 Solving the Recurrence Running time for MergeSort:  b if n = 1 T (n) = 2T (n/2) + cn if n > 1 Apply repeated substitution to guess a solution to the recurrence (that can be formally proved via induction): (i = 1) T (n) = 2T (n/2) + cn CIS 3490 6/7 Solving the Recurrence Running time for MergeSort:  b if n = 1 T (n) = 2T (n/2) + cn if n > 1 Apply repeated substitution to guess a solution to the recurrence (that can be formally proved via induction): (i = 1) T (n) = 2T (n/2) + cn T (n/2) = 2T (n/4) + cn/2 CIS 3490 6/7 Solving the Recurrence Running time for MergeSort:  b if n = 1 T (n) = 2T (n/2) + cn if n > 1 Apply repeated substitution to guess a solution to the recurrence (that can be formally proved via induction): (i = 1) T (n) = 2T (n/2) + cn T (n/2) = 2T (n/4) + cn/2 (i = 2) T (n) = 4T (n/4) + 2cn CIS 3490 6/7 Solving the Recurrence Running time for MergeSort:  b if n = 1 T (n) = 2T (n/2) + cn if n > 1 Apply repeated substitution to guess a solution to the recurrence (that can be formally proved via induction): (i = 1) T (n) = 2T (n/2) + cn T (n/2) = 2T (n/4) + cn/2 (i = 2) T (n) = 4T (n/4) + 2cn T (n/4) = 2T (n/8) + cn/4 CIS 3490 6/7 Solving the Recurrence Running time for MergeSort:  b if n = 1 T (n) = 2T (n/2) + cn if n > 1 Apply repeated substitution to guess a solution to the recurrence (that can be formally proved via induction): (i = 1) T (n) = 2T (n/2) + cn T (n/2) = 2T (n/4) + cn/2 (i = 2) T (n) = 4T (n/4) + 2cn T (n/4) = 2T (n/8) + cn/4 (i = 3) T (n) = 8T (n/8) + 3cn CIS 3490 6/7 Solving the Recurrence Running time for MergeSort:  b if n = 1 T (n) = 2T (n/2) + cn if n > 1 Apply repeated substitution to guess a solution to the recurrence (that can be formally proved via induction): (i = 1) T (n) = 2T (n/2) + cn T (n/2) = 2T (n/4) + cn/2 (i = 2) T (n) = 4T (n/4) + 2cn T (n/4) = 2T (n/8) + cn/4 (i = 3) T (n) = 8T (n/8) + 3cn T (n/8) = 2T (n/16) + cn/8 CIS 3490 6/7 Solving the Recurrence Running time for MergeSort:  b if n = 1 T (n) = 2T (n/2) + cn if n > 1 Apply repeated substitution to guess a solution to the recurrence (that can be formally proved via induction): (i = 1) T (n) = 2T (n/2) + cn T (n/2) = 2T (n/4) + cn/2 (i = 2) T (n) = 4T (n/4) + 2cn T (n/4) = 2T (n/8) + cn/4 (i = 3) T (n) = 8T (n/8) + 3cn T (n/8) = 2T (n/16) + cn/8 (i = 4) T (n) = 16T (n/16) + 4cn ··· (i = j) T (n) = 2j T (n/2j ) + jcn (Guessing the pattern after j substitutions) CIS 3490 6/7 Solving the Recurrence Running time for MergeSort:  b if n = 1 T (n) = 2T (n/2) + cn if n > 1 Apply repeated substitution to guess a solution to the recurrence (that can be formally proved via induction): (i = 1) T (n) = 2T (n/2) + cn T (n/2) = 2T (n/4) + cn/2 (i = 2) T (n) = 4T (n/4) + 2cn T (n/4) = 2T (n/8) + cn/4 (i = 3) T (n) = 8T (n/8) + 3cn T (n/8) = 2T (n/16) + cn/8 (i = 4) T (n) = 16T (n/16) + 4cn ··· (i = j) T (n) = 2j T (n/2j ) + jcn (Guessing the pattern after j substitutions) We reach the base case when n/2j = 1 or j = log n. CIS 3490 6/7 Solving the Recurrence Running time for MergeSort:  b if n = 1 T (n) = 2T (n/2) + cn if n > 1 Apply repeated substitution to guess a solution to the recurrence (that can be formally proved via induction): (i = 1) T (n) = 2T (n/2) + cn T (n/2) = 2T (n/4) + cn/2 (i = 2) T (n) = 4T (n/4) + 2cn T (n/4) = 2T (n/8) + cn/4 (i = 3) T (n) = 8T (n/8) + 3cn T (n/8) = 2T (n/16) + cn/8 (i = 4) T (n) = 16T (n/16) + 4cn ··· (i = j) T (n) = 2j T (n/2j ) + jcn (Guessing the pattern after j substitutions) We reach the base case when n/2j = 1 or j = log n. Thus: T (n) = nT (1) + cn log n = bn + cn log n Theorem MergeSort on a sequence of n elements runs in O(n log n) time. CIS 3490 6/7 Visualizing the Recurrence Exercise: What if n is not a power of 2? CIS 3490 7/7