The Central Idea
A divide-and-conquer algorithm usually has three stages:
- Divide: split the problem into smaller subproblems.
- Conquer: solve the smaller subproblems, often recursively.
- Combine: assemble the smaller answers into a solution to the original problem.
The success of the method depends on choosing a useful decomposition.
Why Divide a Problem?
A large problem may be difficult to attack directly.
If it can be separated into smaller instances of the same type, then the same solution method can be reused at each scale.
This produces a recursive structure:
\[ \text{large problem} \longrightarrow \text{smaller problems} \longrightarrow \text{still smaller problems}. \]Base Cases
Divide-and-conquer algorithms need base cases just as recursive algorithms do.
Once a subproblem becomes small enough, it is solved directly rather than divided again.
For example, a one-element list is already sorted, so it can serve as a base case for a recursive sorting method.
The Divide Step
The divide step determines how the current problem is partitioned.
Common patterns include:
- split a list into two halves;
- split an interval around a midpoint;
- partition data around a selected pivot;
- divide a geometric region into smaller regions;
- split a set of objects into independent groups.
The Conquer Step
In the conquer step, the smaller subproblems are solved.
If a subproblem is still large, the same divide-and-conquer procedure may be applied recursively.
If a subproblem has reached a base case, it is solved directly.
The Combine Step
The combine step turns solutions to the smaller subproblems into a solution to the original problem.
Depending on the algorithm, combining may be:
- trivial;
- a simple comparison;
- a merging process;
- a numerical operation;
- a geometric reconstruction.
Not Every Divide-and-Conquer Algorithm Has a Difficult Combine Step
Binary search is a divide-and-conquer algorithm in which the combine step is essentially unnecessary.
After determining which half can contain the target, the other half is discarded.
The answer to the chosen subproblem is already the answer to the original search problem.
Binary Search as Divide and Conquer
Suppose a sorted list has \(n\) entries.
Binary search:
- examines a middle entry;
- discards the half that cannot contain the target;
- recursively or iteratively searches the remaining half.
Each step reduces the problem size from about \(n\) to about
\[ \frac{n}{2}. \]Repeated Halving
If a problem of size \(n\) is repeatedly reduced by half, the sequence of sizes is approximately
\[ n,\quad \frac{n}{2},\quad \frac{n}{4},\quad \frac{n}{8},\ldots. \]After \(k\) divisions, the size is roughly
\[ \frac{n}{2^k}. \]The process reaches constant size when
\[ 2^k\approx n. \]Logarithmic Depth
From
\[ 2^k\approx n, \]we obtain
\[ k\approx \log_2 n. \]Therefore, repeated halving produces a recursion depth that grows logarithmically with the input size.
Merge Sort
Merge sort is a classic divide-and-conquer sorting algorithm.
Its structure is:
- divide the list into two halves;
- sort each half recursively;
- merge the two sorted halves.
The merge step is the key combine operation.
Dividing a List for Merge Sort
Consider
\[ 8,\ 3,\ 7,\ 4,\ 9,\ 2,\ 6,\ 5. \]Divide into
\[ 8,\ 3,\ 7,\ 4 \]and
\[ 9,\ 2,\ 6,\ 5. \]Each half is then divided again until one-element lists remain.
One-Element Lists Are Base Cases
A one-element list such as
\[ [8] \]is already sorted.
Therefore, merge sort does not need to divide it further.
The recursive division eventually reaches these trivial sorted lists.
Merging Two Sorted Lists
Suppose we have the sorted lists
\[ 2,\ 6,\ 9 \]and
\[ 3,\ 5,\ 8. \]Compare the smallest remaining entries of the two lists.
Since
\[ 2<3, \]place \(2\) first.
Continuing the Merge
The remaining lists are
\[ 6,\ 9 \]and
\[ 3,\ 5,\ 8. \]Choose \(3\), then \(5\), then compare \(6\) and \(8\).
Continuing gives
\[ \boxed{2,\ 3,\ 5,\ 6,\ 8,\ 9}. \]Why the Merge Step Works
Each input list is already sorted.
Therefore, the smallest remaining element overall must be at the front of one of the two lists.
Selecting the smaller front element preserves sorted order and cannot skip a smaller hidden element behind it.
Merge Sort Example
Sort
\[ 6,\ 2,\ 8,\ 3. \]Divide:
\[ [6,2],\qquad[8,3]. \]Divide again:
\[ [6],\ [2],\ [8],\ [3]. \]Merge:
\[ [2,6],\qquad[3,8]. \]Merge again:
\[ \boxed{[2,3,6,8]}. \]Recursion Trees
The recursive structure of a divide-and-conquer algorithm can often be represented by a recursion tree.
Each node represents one problem instance.
Its children represent the subproblems created by division.
The leaves represent base cases.
A Balanced Recursion Tree
Suppose each problem of size \(n\) is divided into two subproblems of size
\[ \frac{n}{2}. \]The first level has \(1\) problem, the next has \(2\), then \(4\), then \(8\), and so on.
The number of levels is approximately
\[ \log_2 n. \]Work Per Level
In merge sort, each level of the recursion tree collectively processes all \(n\) entries during merging.
Thus the work per level is proportional to
\[ n. \]Since there are approximately
\[ \log_2 n \]levels, the total work grows on the order of
\[ n\log n. \]Recurrence Relations for Running Time
The work of a recursive divide-and-conquer algorithm can often be described by a recurrence.
A simplified merge-sort recurrence is
\[ T(n)=2T\left(\frac{n}{2}\right)+cn, \]where:
- the two recursive terms represent sorting the two halves;
- \(cn\) represents the merge work.
General Divide-and-Conquer Recurrence
A common form is
\[ T(n)=aT\left(\frac{n}{b}\right)+f(n), \]where:
- \(a\) is the number of recursive subproblems;
- \(n/b\) is the approximate size of each subproblem;
- \(f(n)\) is the nonrecursive work for dividing and combining.
Later complexity analysis will study such recurrences more systematically.
Balanced Division Matters
Divide-and-conquer methods often perform best when subproblems are reasonably balanced in size.
Splitting
\[ n \]into two parts near
\[ \frac{n}{2} \]produces a shallow recursion tree.
Extremely uneven divisions can create much deeper recursion.
Quicksort Intuition
Quicksort is another important divide-and-conquer sorting method.
It selects a pivot and partitions the remaining entries into groups such as:
\[ \text{less than pivot} \]and
\[ \text{greater than pivot}. \]The groups are then sorted recursively.
The Quality of a Pivot Matters
If the pivot produces two similarly sized partitions, recursion remains relatively balanced.
If the pivot repeatedly produces one very small partition and one very large partition, the recursion can become deep.
Divide-and-conquer performance therefore depends not only on whether a problem is divided, but also on how it is divided.
Maximum by Divide and Conquer
To find the maximum value in a list:
- split the list into two halves;
- find the maximum of each half recursively;
- compare the two maxima.
The larger of the two is the maximum of the original list.
Example: Maximum of a List
Consider
\[ 7,\ 2,\ 11,\ 5,\ 9,\ 4. \]Divide into
\[ 7,\ 2,\ 11 \]and
\[ 5,\ 9,\ 4. \]The recursive maxima are
\[ 11 \]and
\[ 9. \]Therefore,
\[ \boxed{\max=11}. \]Divide-and-Conquer Correctness
Correctness is often proved inductively.
A common structure is:
- prove the base cases are correct;
- assume recursive calls correctly solve smaller subproblems;
- prove that the combine step correctly constructs a solution to the larger problem.
This closely mirrors the recursive organization of the algorithm.
Correctness of Merge Sort
For merge sort:
- one-element lists are correctly sorted;
- by the recursive assumption, both halves are sorted correctly;
- the merge procedure combines two sorted lists into one sorted list without losing or duplicating entries.
Therefore, the entire output is a sorted permutation of the input.
Termination
A divide-and-conquer algorithm terminates when every recursive call operates on a strictly smaller valid problem and repeated division eventually reaches a base case.
A natural progress measure is the problem size.
If that size decreases on every recursive branch, infinite recursion is avoided.
Independent Subproblems
Divide-and-conquer works especially cleanly when subproblems can be solved largely independently.
The algorithm can focus on each subproblem separately and combine results afterward.
If subproblems overlap heavily, repeatedly solving the same smaller problems can waste work.
Overlapping Subproblems
Suppose two recursive branches repeatedly request answers to the same smaller subproblems.
A plain divide-and-conquer method may recompute those answers.
This situation suggests a different strategy:
store and reuse previously computed subproblem solutions.
That idea leads directly to dynamic programming.
Divide-and-Conquer Versus Greedy Methods
Greedy methods commit to one locally attractive choice.
Divide-and-conquer methods split the problem into smaller parts and solve those parts.
Their defining ideas are different:
- greedy: choose and commit;
- divide and conquer: split, solve, combine.
Divide-and-Conquer Versus Dynamic Programming
Both strategies solve smaller subproblems.
The key distinction is that divide-and-conquer subproblems are often mostly independent, while dynamic programming is especially useful when the same subproblems recur.
Dynamic programming avoids repeated work by storing subproblem results.
Divide-and-Conquer Versus Backtracking
Divide-and-conquer generally solves all required subproblems and combines their results.
Backtracking explores alternatives in a search space and may abandon a branch when it cannot lead to a valid solution.
One method decomposes; the other explores choices.
Parallelism
Independent divide-and-conquer subproblems may sometimes be solved simultaneously.
For example, two halves of a large dataset may be processed separately before their results are combined.
This makes divide-and-conquer an important conceptual foundation for parallel computation.
Memory Considerations
Recursive divide-and-conquer algorithms use call-stack space.
Some also require temporary storage for combining results.
Merge sort, for example, commonly uses additional space while merging.
Time efficiency and space efficiency must therefore be considered separately.
Common Error: Dividing Without Simplifying
Splitting a problem is useful only if the resulting subproblems are easier or smaller.
If each recursive call receives essentially the same-sized problem, the algorithm may fail to terminate or may provide no advantage.
Common Error: Forgetting the Combine Step
Solving smaller pieces does not automatically solve the original problem.
In merge sort, sorting the two halves is not enough.
The two sorted halves must still be merged into one sorted sequence.
Common Error: Combining Incorrectly
The combine step must preserve the properties required by the original problem.
A merge procedure that loses duplicates or places entries out of order would invalidate the entire sorting algorithm, even if the recursive halves were sorted correctly.
Common Error: Assuming Every Split Should Be Equal
Balanced splits are often desirable, but equal halves are not required by the definition of divide and conquer.
Some algorithms divide according to pivots, geometry, or structural boundaries.
The correct split depends on the problem.
Common Error: Ignoring Repeated Subproblems
If different recursive branches repeatedly solve the same subproblem, plain divide and conquer may perform unnecessary work.
This is a signal that memoization or dynamic programming may be more appropriate.
Common Error: Confusing Recursion with Divide and Conquer
Not every recursive algorithm is divide and conquer.
A recursive factorial algorithm makes one smaller call:
\[ n!\to(n-1)!. \]Divide-and-conquer usually emphasizes splitting a problem into multiple or substantially reduced parts and then combining their solutions.
A Reliable Procedure for Designing Divide and Conquer
- Identify a direct base case.
- Determine how to split a large input into smaller subproblems.
- Ensure each subproblem is genuinely smaller.
- Specify how each subproblem is solved.
- Specify exactly how subproblem solutions are combined.
- Trace the process on a small example.
- Verify that repeated splitting reaches the base case.
- Check whether the subproblems overlap substantially.
- Estimate the recursion depth.
- Estimate the work done at each level.
Example: Recursive Minimum
To find the minimum of
\[ 8,\ 3,\ 12,\ 1,\ 6,\ 5, \]divide into
\[ 8,\ 3,\ 12 \]and
\[ 1,\ 6,\ 5. \]The recursive minima are
\[ 3 \]and
\[ 1. \]Compare them:
\[ \boxed{\min=1}. \]Example: Divide-and-Conquer Sum
A list sum can also be computed by splitting the list into two parts.
For
\[ 4,\ 7,\ 2,\ 5, \]divide into
\[ 4,\ 7 \]and
\[ 2,\ 5. \]The two sums are
\[ 11 \]and
\[ 7. \]Combine:
\[ \boxed{11+7=18}. \]Example: Counting Recursion Levels
Suppose a problem of size \(64\) is repeatedly halved:
\[ 64,\ 32,\ 16,\ 8,\ 4,\ 2,\ 1. \]There are
\[ \boxed{6} \]halving steps from \(64\) to \(1\).
This agrees with
\[ \log_2 64=6. \]Practice 1: Identify the Three Stages
Name the three standard stages of a divide-and-conquer algorithm.
Practice 2: Binary Search
A sorted list contains \(32\) entries.
After one binary-search division, approximately how many entries remain in the active search interval?
Practice 3: Repeated Halving
Starting from problem size \(128\), how many halving steps are needed to reach size \(1\)?
Practice 4: Merge Two Sorted Lists
Merge
\[ 1,\ 6,\ 10 \]and
\[ 2,\ 4,\ 9. \]Practice 5: Merge Sort
Use merge-sort reasoning to sort
\[ 7,\ 3,\ 5,\ 1. \]Practice 6: Recurrence Interpretation
In
\[ T(n)=2T\left(\frac{n}{2}\right)+cn, \]what do the two major terms represent?
Practice 7: Balanced Versus Unbalanced
Why are balanced divisions often preferable in divide-and-conquer algorithms?
Practice 8: Overlapping Subproblems
What algorithmic concern arises if different recursive branches repeatedly solve the same smaller problems?
Practice 9: Correctness
What must be shown about the combine step when proving a divide-and-conquer algorithm correct?
Practice 10: Classify the Method
An algorithm splits a list into two halves, recursively computes the maximum of each half, and returns the larger of the two results.
Why is this a divide-and-conquer algorithm?
Practice Answers
Practice 1
The three stages are
\[ \boxed{\text{divide, conquer, combine}}. \]Practice 2
One binary-search division keeps approximately half the entries:
\[ \frac{32}{2}=\boxed{16}. \]Practice 3
Since
\[ 128=2^7, \]the number of halving steps is
\[ \boxed{7}. \]Practice 4
Merging in increasing order gives
\[ \boxed{1,\ 2,\ 4,\ 6,\ 9,\ 10}. \]Practice 5
Divide:
\[ [7,3],\qquad[5,1]. \]Divide again:
\[ [7],\ [3],\ [5],\ [1]. \]Merge:
\[ [3,7],\qquad[1,5]. \]Final merge:
\[ \boxed{[1,3,5,7]}. \]Practice 6
The term
\[ 2T\left(\frac{n}{2}\right) \]represents two recursive subproblems of half the original size.
The term
\[ cn \]represents the nonrecursive work, such as dividing or merging.
Practice 7
Balanced divisions tend to keep the recursion tree shallow. Repeatedly splitting roughly in half produces logarithmic depth instead of a long chain of highly uneven recursive calls.
Practice 8
Repeated subproblems can cause wasted recomputation. This suggests storing and reusing subproblem solutions, as in
\[ \boxed{\text{dynamic programming}}. \]Practice 9
It must be shown that combining correct subproblem solutions produces a correct solution to the larger original problem while preserving all required constraints and data.
Practice 10
It divides the original list into smaller lists, solves the same maximum problem recursively on each half, and combines the two answers with one final comparison.
What to Remember
- Divide and conquer follows the pattern divide, conquer, combine.
- Each recursive subproblem must be smaller and eventually reach a base case.
- Binary search uses repeated halving with a trivial combine step.
- Merge sort divides a list, recursively sorts the halves, and merges them.
- Recursion trees reveal the depth and work distribution of recursive algorithms.
- Balanced splitting often leads to shallow recursion.
- Running-time recurrences describe recursive work mathematically.
- Heavy overlap among subproblems may indicate that dynamic programming is a better strategy.
The most important habit is to ask: Can this problem be split into smaller problems whose solutions can be combined cleanly?
Where We Go Next
Divide-and-conquer algorithms solve smaller subproblems independently and combine the results. Some recursive problems behave differently: the same subproblems appear again and again.
The next lesson, Dynamic Programming, develops overlapping subproblems, optimal substructure, memoization, tabulation, state definitions, and the systematic reuse of previously computed results.