Must it run on several computers?

No. A single processor can execute all the subproblems sequentially.

Is every recursive function divide and conquer?

No. Recursion is a programming mechanism; this strategy additionally requires a suitable decomposition and reconstruction of the answer.

Does it always use little memory?

No. The ordinary array merge-sort implementation needs temporary storage for merging. The memory requirements depend on the algorithm and implementation.

AI Glossary / Mathematics and optimization / Advanced

Divide-and-conquer algorithm

Definition

A divide-and-conquer algorithm solves a problem by splitting it into smaller instances, solving those instances, and combining their answers. The smaller instances are often handled recursively until they become simple enough to solve directly. Correctness depends on both the subproblem solutions and the rule used to combine them.

What it means

The approach is more precise than simply dividing a workload among people or computers. The pieces must preserve the information needed for the original answer. Their results must also be combined correctly. Dividing work can expose opportunities for parallel execution, but it does not by itself eliminate coordination, data movement, or the final combination step.

How it works

Define a base case, a decomposition into smaller problems, and a combination procedure. Ensure that repeated decomposition reaches the base case. For merge sort, split a list into halves, sort each half, and merge the sorted results. With balanced halves and linear merging work, its running-time recurrence is T(n)=2T(n/2)+Theta(n), giving Theta(n log n). This is a property of that algorithm and cost model, not a universal running time for every divide-and-conquer method.

Three practical examples

A fictional records service sorts two portions of a customer list and merges them into one ordered list. Simply appending the sorted portions would not establish overall order when their key ranges overlap.
A fictional reporting job computes a total by splitting transactions into disjoint groups, computing group totals, and adding them. The design must ensure that each transaction appears exactly once and that all groups use the same units.
A fictional product system combines ranked results from separate catalog segments. If each segment supplies only an arbitrary subset, the combination may omit an item that belongs in the global result. The subproblem output must be sufficient for the precise ranking task.

Think of it this way

Imagine sorting a stack of numbered cards by repeatedly making smaller stacks. Once each small stack is ordered, compare the first remaining cards and take the smaller one to build a larger ordered stack. The important operation is that comparison-based merge. Placing ordered stacks side by side is not enough unless their number ranges already line up.

Worked example

Sort the invented list [9,3,7,1,8,2,6,4] using merge sort. Split it into [9,3,7,1] and [8,2,6,4], then into pairs, and finally into single-item lists. A single-item list is already sorted.
The four pair merges produce [3,9], [1,7], [2,8], and [4,6]. Each requires one comparison between values, for four comparisons at this level.
Merge [3,9] with [1,7]. Compare 3 with 1, then 3 with 7, then 9 with 7. The result is [1,3,7,9], using three comparisons. Similarly, merging [2,8] and [4,6] produces [2,4,6,8] with three comparisons.
The final merge compares the current first remaining elements of these two four-item lists. It selects 1,2,3,4,6,7,8 in order, after which 9 is appended from the remaining list. This merge uses seven comparisons.
The complete result is [1,2,3,4,6,7,8,9]. The total number of value comparisons in this trace is 4+3+3+7=17. That count excludes copying, allocation, index checks, and function-call overhead. It is an exact count for the stated input and merge procedure, not a formula saying that every eight-item input uses 17 comparisons.

Illustrative case study

In a fictional data-cleaning exercise, two workers independently sort the left and right halves of the example. A coordinator first concatenates their results, producing [1,3,7,9,2,4,6,8]. Both halves are sorted, but the combined list is not: 9 precedes 2.
The team replaces concatenation with the seven-comparison merge. It then tests three requirements separately: output order, preservation of every input item, and the handling of duplicate keys. For records with equal keys, it specifies whether their original relative order must be preserved and implements the tie rule accordingly.
The team also measures elapsed time before making a speed claim. Two simultaneous workers might shorten the sorting phase, but their outputs still require transfer and merging. The tiny list is a correctness demonstration, not a performance benchmark showing that parallel execution is beneficial at this size.

Common misconceptions and mistakes

Dividing into smaller pieces does not automatically make the overall procedure faster. Splitting and combining can dominate the work.
Correct subproblem answers do not ensure a correct final answer. The case study's concatenation error demonstrates the missing obligation.
The recurrence for merge sort must not be copied into a different algorithm without checking the number and size of subproblems and the combination cost.
Recursive code needs a base case and genuine progress toward it. Repeatedly calling the same-sized problem would not terminate merely because the code is labeled divide and conquer.
Equal-key ordering is a separate requirement from numerical sorting. A merge can preserve it through a suitable tie rule, but the broad strategy alone does not specify that rule.

Business use

For a proposed decomposition, ask what each subtask receives, what it must return, and how the final answer is verified. The reporting example requires disjoint transaction groups; the sorting example requires a true merge. Estimate end-to-end cost, including intermediate storage and transfers, before predicting speedup. A clear combination contract makes independently developed components easier to review and helps distinguish computational savings from work merely shifted elsewhere.

Check your understanding

Why is concatenating the two sorted four-item lists wrong?

Answer: Their value ranges overlap, so the boundary does not preserve order.

How many value comparisons occur in the final merge?

Answer: Seven.

What is the base case in the example?

Answer: A list with at most one item, which is already sorted.

Related terms

Parallel algorithm
Decomposition
Dynamic programming
Recursion
base case
merge sort
recurrence relation
algorithmic complexity
correctness

Learn next

Repeat the merge trace with [1,2,3,4,6,7,8,9] already sorted and count the value comparisons. Then examine an odd-length input and specify how the split handles the extra item. These checks reveal implementation details hidden by the simplified equal-halves recurrence.

Sources

MIT 6.006 Introduction to Algorithms, Spring 2020, Recitation 3, merge sort, recurrence, memory, and stability discussion: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/1869dbf640ded6b31f1bd369d2001ef5_MIT6_006S20_r03.pdf The eight-item input, exact comparison trace, and business scenarios are original illustrations.

Previous: Divergence-from-randomness model Next: Division model (Fitzgibbon)