Divide And Conquer A large instance is solved as follows:
Divide the large instance into smaller instances.
Solve the smaller instances somehow.
Combine the results of the smaller instances to obtain the result for the original large instance.
A small instance is solved in some other way.
Divide And Conquer A large instance is solved as follows:
Divide the large instance into smaller instances.
Solve the smaller instances somehow.
Combine the results of the smaller instances to obtain the result for the original large instance.
A small instance is solved in some other way.
Small And Large Instance Small instance.
Sort a list that has n <= 10 elements.
Find the minimum of n <= 2 elements.
Large instance.
Sort a list that has n > 10 elements.
Find the minimum of n > 2 elements.
Solving A Small Instance A small instance is solved using some direct/simple strategy.
Sort a list that has n <= 10 elements.
Use count, insertion, bubble, or selection sort.
Find the minimum of n <= 2 elements.
When n = 0, there is no minimum element.
When n = 1, the single element is the minimum.
When n = 2, compare the two elements and determine which is smaller.
Solving A Large Instance A large instance is solved as follows:
Divide the large instance into k >= 2 smaller instances.
Solve the smaller instances somehow.
Combine the results of the smaller instances to obtain the result for the original large instance.
Sort A Large List Sort a list that has n > 10 elements.
Sort 15 elements by dividing them into 2 smaller lists.
One list has 7 elements and the other has 8.
Sort these two lists using the method for small lists.
Merge the two sorted lists into a single sorted list.
Find The Min Of A Large List Find the minimum of 20 elements.
Divide into two groups of 10 elements each.
Find the minimum element in each group somehow.
Compare the minimums of each group to determine the overall minimum.
Recursion In Divide And Conquer Often the smaller instances that result from the divide step are instances of the original problem (true for our sort and min problems). In this case,
If the new instance is a small instance, it is solved using the method for small instances.
If the new instance is a large instance, it is solved using the divide-and-conquer method recursively.
Generally, performance is best when the smaller instances that result from the divide step are of approximately the same size.
Recursive Find Min Find the minimum of 20 elements.
Divide into two groups of 10 elements each.
Find the minimum element in each group recursively. The recursion terminates when the number of elements is <= 2. At this time the minimum is found using the method for small instances.
Compare the minimums of each group to determine the overall minimum.
Merge Sort
k = 2
First (n/2) elements define one of the smaller instances; remaining (n/2) elements define the second smaller instance.
Each of the two smaller instances is sorted recursively.
The sorted smaller instances are combined using a process called merge.
Complexity is O(n log n).
Usually implemented nonrecursively.
Merge Two Sorted Lists
A = (2, 5, 6)
B = (1, 3, 8, 9, 10)
C = ()
Compare smallest elements of A and B and merge smaller into C.
A = (2, 5, 6)
B = (3, 8, 9, 10)
C = (1)
Merge Two Sorted Lists
A = (5, 6)
B = (3, 8, 9, 10)
C = (1, 2)
A = (5, 6)
B = (8, 9, 10)
C = (1, 2, 3)
A = (6)
B = (8, 9, 10)
C = (1, 2, 3, 5)
Merge Two Sorted Lists
A = ()
B = (8, 9, 10)
C = (1, 2, 3, 5, 6)
When one of A and B becomes empty, append the other list to C.
O(1) time needed to move an element into C.
Total time is O(n + m), where n and m are, respectively, the number of elements initially in A and B.
Let t(n) be the time required to sort n elements.
t(0) = t(1) = c, where c is a constant.
When t > 1,
t(n) = t((n/2)) + t((n/2)) + dn,
where d is a constant.
To solve the recurrence, assume n is a power of 2 and use repeated substitution.
Merge Sort
time complexity
t(n) = 2 t(n/2) + n
= 2 × (2t(n/4) + n/2) + n
= 22 t(n/4) + n + n
= 23 t(n/8) + 3n
…
= 2log n t(n/n) + (log n) ×n
= n × t(1) + n(log n) (note: t(1) = O(1))
= O(n log n)
Merge Sort
Downward pass over the recursion tree.
Divide large instances into small ones.
Upward pass over the recursion tree.
Merge pairs of sorted lists.
Number of leaf nodes is n.
Number of nonleaf nodes is n-1.
Time Complexity
Downward pass.
O(1) time at each node.
O(n) total time at all nodes.
Upward pass.
O(n) time merging at each level that has a nonleaf node.
Number of levels is O(log n).
Total time is O(n log n).
Comments