Why is mergesort O(n log n)?

Mergesort divides the array into two halves (log n levels of recursion) and at each level does linear-time merging across all elements, giving the recurrence T(n) = 2T(n/2) + O(n), which the master theorem solves as O(n log n).

Is quicksort a divide-and-conquer algorithm even though it has no explicit combine step?

Yes. Quicksort does its main work in the divide step via partitioning around a pivot; once the two partitions are sorted recursively, no combine work is needed. The paradigm allows the bulk of the effort to fall in any of the three phases.

Divide and Conquer

Divide and conquer is an algorithm design paradigm that solves a problem by splitting it into smaller subproblems of the same type, solving them recursively, and combining their solutions into a solution for the original problem.

PaperMind(으)로 주제 찾기곧 제공Find papers & topics

Tools & resources

슬라이드 다운로드

Learn & explore

동영상곧 제공

Definition

A divide-and-conquer algorithm recursively breaks a problem into two or more subproblems of the same or related type until the subproblems are simple enough to solve directly, then combines the subproblem solutions to produce the answer to the original problem.

Scope

This topic covers the three-step structure of divide-and-conquer algorithms (divide, conquer, combine), canonical examples such as mergesort, quicksort, binary search and fast integer and matrix multiplication, and the recurrence-based analysis of their running times. It connects closely to the master theorem and recurrence-solving techniques used to analyze such algorithms.

Core questions

How is a problem decomposed so that subproblems are independent and of the same form?
What work is done in the combine step, and how does it affect total cost?
How are the resulting recurrences solved to obtain asymptotic running times?
When does divide-and-conquer beat a straightforward iterative approach?

Key concepts

divide, conquer, combine
recurrence relations
master theorem
mergesort
quicksort
binary search
Karatsuba multiplication
Strassen's matrix multiplication

Key theories

Master theorem for recurrences: The master theorem gives closed-form asymptotic solutions for divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n) by comparing the cost of the recursive subproblems against the combine cost f(n).
Subquadratic multiplication via decomposition: Recursively splitting operands and reducing the number of recursive multiplications (as in Karatsuba multiplication and Strassen's matrix multiplication) yields asymptotically faster algorithms than the naive quadratic and cubic methods.

Clinical relevance

Divide-and-conquer underlies many of the most widely deployed algorithms: efficient sorting (mergesort, quicksort) in standard libraries, binary search in lookup routines, the Fast Fourier Transform in signal and image processing, and fast multiplication used in cryptography and arbitrary-precision arithmetic.

History

Mergesort is attributed to John von Neumann (1945). C. A. R. Hoare published quicksort in 1962. Karatsuba's 1960 subquadratic multiplication and Strassen's 1969 matrix-multiplication algorithm demonstrated that recursive decomposition could beat classical bounds, helping establish divide-and-conquer as a foundational paradigm.

Key figures

C. A. R. Hoare
John von Neumann
Anatoly Karatsuba
Volker Strassen

Seminal works

hoare1962
cormen2009

Frequently asked questions

Why is mergesort O(n log n)?: Mergesort divides the array into two halves (log n levels of recursion) and at each level does linear-time merging across all elements, giving the recurrence T(n) = 2T(n/2) + O(n), which the master theorem solves as O(n log n).
Is quicksort a divide-and-conquer algorithm even though it has no explicit combine step?: Yes. Quicksort does its main work in the divide step via partitioning around a pivot; once the two partitions are sorted recursively, no combine work is needed. The paradigm allows the bulk of the effort to fall in any of the three phases.