REFERENCE SHEET

Sorting, binary search & lower bounds

Use ordering to narrow possibilities, and distinguish algorithm cost from unavoidable cost.

Before this Asymptotics & recurrences, Recursion, invariants & termination

comparison sorting: worst-case comparisons ≥ ⌈log₂(n!)⌉ = Ω(n log n)

Definitions

Comparison model

The algorithm learns key order only through comparisons. Lower bounds in this model do not automatically apply to algorithms that inspect digits or exploit a bounded key range.

Stable sorting

Equal-key records retain their original relative order.

Binary search

Maintain an interval of possible positions in a sorted random-access sequence; each comparison discards about half the remaining candidates.

Key theorems

Sorting decision-tree bound

A deterministic comparison sort of n distinct keys needs at least n! leaves, one per possible ordering, hence worst-case depth at least ⌈log₂(n!)⌉.

Mergesort

Merging two sorted runs takes linear time; the balanced recurrence gives Θ(n log n) worst-case time. Standard array mergesort uses O(n) auxiliary storage.

Binary search bound

Sorted-array membership uses O(log n) comparisons and O(1) extra space in an iterative implementation. The maintained interval must shrink on every unsuccessful iteration.

Notable applications

Indexes

Sorted keys support membership, boundaries, and range queries.

Multi-key ordering

Stable sorting lets a later primary-key sort preserve a previous secondary-key order within equal primary keys.

Work it out

Try before revealing

01 / Trace

Using a half-open candidate interval [lo,hi), find the first index with value ≥6 in [1,3,6,6,9].

Hint

When a[mid]≥6, move hi to mid; otherwise move lo to mid+1.

Solution

Start [0,5): mid=2 so hi=2. Then mid=1 and a[1]=3, so lo=2. The interval is empty at 2, the desired boundary.

02 / Reason

Why does counting sort on keys in {0,…,k−1} not contradict the comparison-sorting lower bound?