CSC3160: Design and Analysis of Algorithms Week 7: Divide and Conquer Instructor: Shengyu Zhang 1
Instructor: Shengyu Zhang 1
Example 1:Merge sort 2
Example 1: Merge sort 2
Starting example Sorting: We have a list of numbers x1,...,xn. We want to sort them in the increasing order. 3
Starting example ◼ Sorting: ❑ We have a list of numbers 𝑥1, … , 𝑥𝑛. ❑ We want to sort them in the increasing order. 3
An algorithm:merge sort Merge sort: Cut it into two halves with equal size. Suppose 2 divides n for simplicity. Suppose the two halves are sorted:Merge them. Use two pointers,one for each half,to scan them, during which course do the appropriate merge. How to sort each of the two halves?Recursively. 4
An algorithm: merge sort ◼ Merge sort: ❑ Cut it into two halves with equal size. ◼ Suppose 2 divides 𝑛 for simplicity. ❑ Suppose the two halves are sorted: Merge them. ◼ Use two pointers, one for each half, to scan them, during which course do the appropriate merge. ❑ How to sort each of the two halves? Recursively. 4
Complexity? Suppose this algorithm takes T(n)time for an input with n numbers. Thus each of the two halves takes T(n/2) time. The merging?0(n) Scanning n elements,an 0(1)time operation needed for each. Total amount of time:T(n)≤2T(n/2)+c·n. 5
Complexity? ◼ Suppose this algorithm takes 𝑇(𝑛) time for an input with 𝑛 numbers. ◼ Thus each of the two halves takes 𝑇(𝑛/2) time. ◼ The merging? 𝑂(𝑛) ❑ Scanning 𝑛 elements, an 𝑂(1) time operation needed for each. ◼ Total amount of time: 𝑇(𝑛) ≤ 2𝑇(𝑛/2) + 𝑐 ∙ 𝑛. 5