Lesson · Algorithms and Complexity · Analysis

Searching and Sorting

Linear and binary search, three quadratic sorts and merge sort — and the proof that no comparison sort can do better than n log n, which is a statement about the problem rather than about any algorithm.

Open the interactive lesson Practice

linear search Θ(n) binary search Θ(log n), needs SORTED input bubble, selection, insertion Θ(n²) merge sort Θ(n log n) always LOWER BOUND: every comparison sort needs Ω(n log n) comparisons

Algorithms, and a limit

Core ideas

What this lesson establishes

Six algorithms, and then a theorem about every possible algorithm of a certain kind.

Binary search needs sorted input

That is what licenses discarding half the array. On unsorted data it terminates and returns wrong answers.

The quadratic sorts differ in their constants and their adaptivity

Insertion sort is Θ(n) on nearly sorted data; bubble and selection sort do the same work regardless.

n log n is a lower bound, not a target

A decision-tree argument shows no comparison sort can beat it. It is a statement about the problem.

The material

The standard algorithms

Searching, sorting, and the information-theoretic limit.

Searching

linear search check each in turn Θ(n) worst any array binary search halve the range each step Θ(log n) SORTED array

Theorem · Binary search cost

On a sorted array of n elements, binary search performs at most ⌊log₂ n⌋ + 1 comparisons.

Each comparison at least halves the range: from m candidates it leaves at most ⌊m/2⌋. Starting at n, after t comparisons at most ⌊n/2^t⌋ remain, and the search ends when that reaches 0.

So t ≤ log₂ n + 1.

□

Sorting first costs Θ(n log n), so binary search pays for itself only across many searches on the same data — roughly, once the number of searches exceeds log n.

Sorting

bubble compare adjacent, swap, repeat Θ(n²) always selection find the minimum, place it, repeat Θ(n²) always insertion insert each into the sorted prefix Θ(n²) worst, Θ(n) best merge split, sort each half, merge Θ(n log n) always

Insertion sort is the interesting quadratic one: its inner loop stops as soon as it finds a smaller element, so on nearly sorted data it does almost no work. That adaptivity is why real implementations use it below a size threshold.

Merge sort satisfies T(n) = 2T(n/2) + n, which “Divide and Conquer”'s master theorem solves as Θ(n log n). Its cost does not depend on the data at all, and it needs Θ(n) extra space, which is its one drawback.

The lower bound

Theorem · Comparison sorting requires Ω(n log n)

Any sorting algorithm that gets information about the input only by comparing pairs of elements must perform Ω(n log n) comparisons in the worst case.

Model the algorithm as a decision tree: each internal node is a comparison with two outcomes, and each leaf is one possible output ordering. To sort correctly the tree must have at least n! leaves, one per permutation of the input.

A binary tree of height h has at most 2^h leaves — the 2^{h+1} − 1 vertex bound of “Trees”, in Graphs and Trees, restricted to the last level — so a tree with L leaves has height at least log₂ L, and this one has height at least log₂(n!).

The largest n/2 factors of n! are each at least n/2, so n! ≥ (n/2)^{n/2} and log₂(n!) ≥ (n/2) log₂(n/2), which is Ω(n log n). The height is the worst-case number of comparisons, and the bound follows. (Stirling's approximation sharpens this to log₂(n!) ≈ n log₂ n − 1.44n, but the crude bound is all the theorem needs.)

□

This is a genuine impossibility result and it is worth distinguishing from a failure of ingenuity: no comparison sort will ever beat n log n, and merge sort therefore achieves the optimum. Combinatorics and Counting's count of permutations and Graphs and Trees's tree height bound are both doing work in the proof.

Sorts that beat the bound exist and they do not compare. Counting sort and radix sort use the values themselves as indices and run in Θ(n) under assumptions about the key range. They do not contradict the theorem; they fall outside its hypothesis.

Interactive

Algorithms and growth

Counts from running, not from quoting

Three sorts, counted

The lab opens on the worked example: the same shuffled array of 16 through all three algorithms, 120, 77 and 48 comparisons. Change the input order for insertion sort's 15 on sorted input and 120 on reversed, and watch bubble sort not move. Merge sort's column stays below n log₂ n = 64, as the analysis allows. Switch to Search for the other half of the worked example: 16 comparisons against ⌊log₂ 16⌋ + 1 = 5, and 10 at n = 1000 if you extend the table.

What to examine

f(n)

g(n)

Input order

Growth policy

a (subproblems)

b (shrink factor)

d (combining cost n^d)

n16

measured—

predicted—

Method

Choosing a search or a sort

The data decides.

Is the data sorted, and will it be searched often?

If both, sort once and binary search. If neither, linear search is fine and simpler.

How large is the input?

Below a few dozen, insertion sort beats merge sort on constants. Above that the class dominates.

Is the data nearly sorted?

Insertion sort is Θ(n) there and merge sort is still Θ(n log n). Adaptivity is worth real money on partially ordered data.

Is extra space available?

Merge sort needs Θ(n) of it. Where that is unacceptable, heapsort achieves Θ(n log n) in place.

Searching and sorting

Score 0 / 0

Choose the answer you can justify.

Comparison counts at n = 16

Measured by running each algorithm on the same shuffled array.

bubble 120 = n(n−1)/2, exactly — data-independent insertion 77 data-dependent; 15 on sorted input, 120 reversed merge 48 below n log₂ n = 64, as the analysis allows binary search worst case: ⌊log₂ 16⌋ + 1 = 5 linear search worst case: 16 At n = 1000, on the lab's shuffled array: bubble 499 500 insertion 235 149 merge 7 387 binary search worst case ⌊log₂ 1000⌋ + 1 = 10

Merge sort's 48 comparisons is below n log₂ n because the true worst case for n a power of two is n log₂ n − n + 1 = 49, and the analysis quotes the leading term. Measured counts sitting under a predicted curve is normal and not an error; a measured count sitting above it would be.

Common mistakes

Binary searching unsorted dataIt terminates and returns confident wrong answers, which is the most dangerous failure mode.

Believing the lower bound applies to all sortingIt applies to comparison sorts. Counting and radix sort beat it under assumptions about the keys.

Ignoring adaptivityInsertion sort is linear on nearly sorted data. On partially ordered inputs that is worth more than a better asymptotic class.

Check your understanding

✓

Finish when you can state the lower bound and why it holds.

Explain in three sentences why n! leaves force Θ(n log n) height. The argument uses Combinatorics and Counting's permutation count and Graphs and Trees's tree bound, and it is the cleanest impossibility proof on this path.

Note: Timsort, the default sort in Python and Java, is merge sort with insertion sort for small runs and special handling for existing sorted runs. Every element of that design is a response to something in this lesson.