Week-03: Divide-and-Conquer
Technique:
Merge Sort, Quick Sort
CSE-215: Data Structure & Algorithm
II
By Lecturer Md. Mustaqim Abrar
Divide-and-Conquer
● Divide-and-Conquer is a general algorithm design
paradigm:
○ Divide the problem into a number of subproblems
that are smaller instances of the same problem
○ Conquer the subproblems by solving them
recursively
○ Combine the solutions to the subproblems into the
solution for the original problem
● The base case for the recursion are subproblems of
constant size
● Analysis can be done using recurrence equations
2
Merge Sort and Quick Sort
● Two well-known sorting algorithms adopt this divide-
and-conquer strategy
● Merge sort
○ Divide step is trivial – just split the list into two
equal parts
○ Work is carried out in the conquer step by
merging two sorted lists
● Quick sort
○ Work is carried out in the divide step using a pivot
element
○ Conquer step is trivial
3
Merge Sort: Algorithm
4
Merge Sort: Simulation
• Example: 7 2 9 4 3 8 6 1
7 2 9 4 3 8 6 1 → 1 2 3 4 6 7 8 9
7 2 9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6
7 2 → 2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6
7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1
5
Merge Sort: Simulation
• Partition
7 2 9 4⏐3 8 6 1 → 1 2 3 4 6 7 8 9
7 2 9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6
7 2 → 2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6
7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1
6
Merge Sort: Simulation
• Divide into sub problems
7 2 9 4⏐3 8 6 1 → 1 2 3 4 6 7 8 9
7 2⏐9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6
7 2 → 2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6
7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1
7
Merge Sort: Simulation
• Divide into sub problems
7 2 9 4⏐3 8 6 1 → 1 2 3 4 6 7 8 9
7 2⏐9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6
7⏐2 → 2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6
7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1
8
Merge Sort: Simulation
• Conquer the sub problems
7 2 9 4⏐3 8 6 1 → 1 2 3 4 6 7 8 9
7 2⏐9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6
7⏐2 → 2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6
7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1
9
Merge Sort: Simulation
• Conquer the sub problems
7 2 9 4⏐3 8 6 1 → 1 2 3 4 6 7 8 9
7 2⏐9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6
7⏐2 → 2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6
7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1
10
Merge Sort: Simulation
• Combine or Merge the sub problems
7 2 9 4⏐3 8 6 1 → 1 2 3 4 6 7 8 9
7 2⏐9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6
7⏐2 → 2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6
7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1
11
Merge Sort: Simulation
• Divide into sub problems
7 2 9 4⏐3 8 6 1 → 1 2 3 4 6 7 8 9
7 2⏐9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6
7⏐2 → 2 7 9⏐4 → 4 9 3 8 → 3 8 6 1 → 1 6
7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1
12
Merge Sort: Simulation
• Conquer the sub problems
7 2 9 4⏐3 8 6 1 → 1 2 3 4 6 7 8 9
7 2⏐9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6
7⏐2 → 2 7 9⏐4 → 4 9 3 8 → 3 8 6 1 → 1 6
7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1
13
Merge Sort: Simulation
• Combine or Merge the sub problems
7 2 9 4⏐3 8 6 1 → 1 2 3 4 6 7 8 9
7 2⏐9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6
7⏐2 → 2 7 9⏐4 → 4 9 3 8 → 3 8 6 1 → 1 6
7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1
14
Merge Sort: Simulation
• Combine or Merge the sub problems
7 2 9 4⏐3 8 6 1 → 1 2 3 4 6 7 8 9
7 2⏐9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6
7⏐2 → 2 7 9⏐4 → 4 9 3 8 → 3 8 6 1 → 1 6
7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1
15
Merge Sort: Simulation
• Conquer the sub problems
7 2 9 4⏐3 8 6 1 → 1 2 3 4 6 7 8 9
7 2⏐9 4 → 2 4 7 9 3 8 6 1 → 1 3 6 8
7⏐2 → 2 7 9⏐4 → 4 9 3 8 → 3 8 6 1 → 1 6
7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1
16
Merge Sort: Simulation
• Combine or Merge the sub problems
7 2 9 4⏐3 8 6 1 → 1 2 3 4 6 7 8 9
7 2⏐9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6
7⏐2 → 2 7 9⏐4 → 4 9 3 8 → 3 8 6 1 → 1 6
7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1
17
Merge Sort: Algorithm
L is storing the left part of the A[p to r] which starts from p.
R is storing the right part of the A[p to r] which starts from q+1.
18
Merge Sort: Simulation
2 4 1 3 Not
7 6 Red
Merged
9 8
Purple In Decision
Green Merged
Number of element merged: 0
19
Merge Sort: Simulation
2 4 1 3 Not
7 6 Red
Merged
9 8
Purple In Decision
Green Merged
Number of element merged: 0
20
Merge Sort: Simulation
2 4 1 3 Not
7 6 Red
Merged
9 8
Purple In Decision
1
Green Merged
Number of element merged: 1
21
Merge Sort: Simulation
2 4 1 3 Not
7 6 Red
Merged
9 8
Purple In Decision
1 2
Green Merged
Number of element merged: 2
22
Merge Sort: Simulation
2 4 1 3 Not
7 6 Red
Merged
9 8
Purple In Decision
1 2 3
Green Merged
Number of element merged: 3
23
Merge Sort: Simulation
2 4 1 3 Not
7 6 Red
Merged
9 8
Purple In Decision
1 2 3 4
Green Merged
Number of element merged: 4
24
Merge Sort: Simulation
2 4 1 3 Not
7 6 Red
Merged
9 8
Purple In Decision
1 2 3 4 6
Green Merged
Number of element merged: 5
25
Merge Sort: Simulation
2 4 1 3 Not
7 6 Red
Merged
9 8
Purple In Decision
1 2 3 4 6
7 Green Merged
Number of element merged: 6
26
Merge Sort: Simulation
2 4 1 3 6 Not
7 8 Red
Merged
9 ∞
Purple In Decision
1 2 3 4 6
7 8 Green Merged
Number of element merged: 7
27
Merge Sort: Simulation
2 4 1 3 6 Not
7 8 Red
Merged
9 ∞
Purple In Decision
1 2 3 4 6
7 8 9 Green Merged
Number of element merged: 8
28
Merge Sort: Running Time
● The recurrence for the worst-case running time T(n)
is:
T(n) = Θ(1) if n = 1
2T(n/2) + Θ(n) if n > 1
● equivalently
T(n) = b if n = 1
2T(n/2) + bn if n > 1
● Solve this recurrence by
(1) iteratively expansion
30 (2) using the recursion tree
Merge Sort: Running Time (Iterative Expansion)
● Note that base, T(n) =b, case occurs when 2i = n.
That is, i = log n.
● So,
31
● Thus, T(n) is O(n log n).
Merge Sort: Running Time (Recursion Tree)
● Draw the recursion tree for the recurrence relation
and look for a pattern:
time
depth T’s size
0 1 n bn
1 2 n/2 bn
i 2i n/2i bn
… … … …
Total time = bn + bn log n
32 (last level plus all previous levels)
Quick Sort
● Another divide-and-conquer algorithm
○ The array A[p..r] is partitioned into two non-
empty subarrays A[p..q] and A[q+1..r]
■ Invariant: All elements in A[p..q] are less than all
elements in A[q+1..r]
○ The subarrays are recursively sorted by calls to
quicksort
○ Unlike merge sort, no combining step: two
subarrays form an already-sorted array
33
Quick Sort: Algorithm
34
Quick Sort: Algorithm (Partition)
● Clearly, all the actions take place in the partition()
function
○ Rearranges the subarrays in place
○ End result:
■ Two subarrays
■ All values in first subarray ≤ all values in the
second
○ Returns the index of the “pivot” element
separating the two subarrays
35
Quick Sort: Simulation
• Example: 2 8 7 1 3 5 6 4
2 8 7 1 3 5 6 4
7 2 9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6
7 2 → 2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6
7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1
36
Quick Sort: Simulation
• Select Pivot
2 8 7 1 3 5 6 4
7 2 9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6
7 2 → 2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6
7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1
37
Quick Sort: Simulation
• Divide into sub problems
2 8 7 1 3 5 6 4
2 1 3 4 8 7 5 6
7 2 → 2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6
7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1
38
Quick Sort: Simulation
• Select Pivot
2 8 7 1 3 5 6 4
2 1 3 4 8 7 5 6
7 2 → 2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6
7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1
39
Quick Sort: Simulation
• Divide into sub problems
2 8 7 1 3 5 6 4
2 1 3 4 8 7 5 6
2 1 3 3 8 → 3 8 6 1 → 1 6
7→7 2→2 9→9 4→4 3→3 8→8 6→6 1→1
40
Quick Sort: Simulation
• Divide into sub problems
2 8 7 1 3 5 6 4
2 1 3 4 8 7 5 6
2 1 3 3 8 → 3 8 6 1 → 1 6
1 2 3→3 8→8 6→6 1→1
41
Quick Sort: Simulation
• Select Pivot
2 8 7 1 3 5 6 4
2 1 3 4 8 7 5 6
2 1 3 3 8 → 3 8 6 1 → 1 6
1 2 3→3 8→8 6→6 1→1
42
Quick Sort: Simulation
• Divide into sub problems
2 8 7 1 3 5 6 4
2 1 3 4 8 7 5 6
2 1 3 4 5 6 8 7
1 2 4 5 6 7 8
43 7 8
Quick Sort: Simulation
• No need of Merge, already-sorted array
2 8 7 1 3 5 6 4
2 1 3 4 8 7 5 6
2 1 3 4 5 6 8 7
1 2 4 5 6 7 8
44 7 8
Quick Sort: Algorithm
45
Quick Sort: Algorithm
pivot
From i + 1 to j is a window of elements > A[r].
The cursor j moves right one step at a time.
If the cursor j “discovers” an element ≤ A[r],
then this element is swapped with the front
element of the window, effectively moving the
window right one step; if it discovers an
element > A[r], then the window simply
becomes longer one unit.
46
Quick Sort: Algorithm
47
Quick Sort: Analysis
● What will be the worst case for the algorithm?
○ Partition is always unbalanced
● What will be the best case for the algorithm?
○ Partition is perfectly balanced
● Which is more likely?
○ The latter, by far, except...
● Will any particular input elicit the worst case?
○ Yes: Already-sorted input
48
Quick Sort: Analysis
● In the worst case:
T(1) = Θ(1)
T(n) = T(n - 1) + Θ(n)
Works out to
T(n) = Θ(n2)
● In the best case:
T(1) = Θ(1)
T(n) = 2T(n/2) + Θ(n)
Works out to
T(n) = Θ(n lg n)
49
Quick Sort: Analysis
● The real liability of quicksort is that it runs in O(n2) on
already-sorted input
● Book discusses two solutions:
○ Randomize the input array, OR
○ Pick a random pivot element
● How will these solve the problem?
○ By ensuring that no particular input can be chosen
to make quicksort run in O(n2) time
50
Analyzing Quicksort: Average Case
● Assuming random input, average-case running time is
much closer to O(n lg n) than O(n2)
● First, a more intuitive explanation/example:
○ Suppose that partition() always produces a 9-to-1
split. This looks quite unbalanced!
○ The recurrence is thus:
○ T(n) = T(9n/10) + T(n/10) + n
○ How deep will the recursion go? (draw it)
51
Analyzing Quicksort: Average Case
52
Analyzing Quicksort: Average Case
● Intuitively, a real-life run of quicksort will produce a
mix of “bad” and “good” splits
○ Randomly distributed among the recursion tree
○ Pretend for intuition that they alternate between
best-case (n/2 : n/2) and worst-case (n-1 : 1)
○ What happens if we bad-split root node, then good-
split the resulting size (n-1) node?
53
Analyzing Quicksort: Average Case
● Intuitively, a real-life run of quicksort will produce a
mix of “bad” and “good” splits
○ Randomly distributed among the recursion tree
○ Pretend for intuition that they alternate between
best-case (n/2 : n/2) and worst-case (n-1 : 1)
○ What happens if we bad-split root node, then good-
split the resulting size (n-1) node?
■ We end up with three subarrays, size 1, (n-1)/2, (n-1)/2
■ Combined cost of splits = n + n -1 = 2n -1 = O(n)
■ No worse than if we had good-split the root node!
54
Analyzing Quicksort: Average Case
● Intuitively, the O(n) cost of a bad split (or 2 or 3 bad
splits) can be absorbed into the O(n) cost of each good
split
● Thus running time of alternating bad and good splits is
still O(n lg n), with slightly higher constants
● How can we be more rigorous?
55
Thank You!
56