Sorting & searching

Order, once Three deep dives Advanced: the comparison floor

Sorting and searching are two halves of one bargain. Put a sequence in order once — at a cost of about n log n comparisons — and every later lookup drops from an O(n) scan to an O(log n) binary search. The two best comparison sorts, merge sort and quicksort, are the same divide-and-conquer recursion you met as a tree in F4.02, and binary search is the same halving as a balanced tree’s descent.

The running sequence is the sorted output of F4.02’s search tree, [5, 8, 10, 12, 20, 30, 42]. Three angles open the module: sorting a sequence, searching it, and the cost model that says n log n is the floor.

Insertion sort · one comparison per step

[5, 2, 6, 1, 4, 3, 7]
compare a[0]=5 & a[1]=2 — comparisons: 0 · swaps: 0.

Order, once

An unordered sequence answers “is 20 in here?” only by checking every element. A sorted sequence answers it by halving: look at the middle, then the half that could contain the target. Select an angle to see the sort, the search, and the cost.

The angle · select one

role: rearrange into order

result: [5, 8, 10, 12, 20, 30, 42]

Sorting is work you do once so that searching is cheap forever after. The rest of the module is how each half is built — and why the price of sorting cannot drop below n log n for a comparison sort.

Three deep dives

In order: the two divide-and-conquer sorts; linear versus binary search; then stability and the cost model that ranks one sort against another.

F4.03.1

Merge & quicksort

Two divide-and-conquer sorts: merge splits and combines, quicksort partitions around a pivot — the tree-fold recursion from F4.02, applied to a list.

F4.03.2

Linear & binary search

O(n) over anything, O(log n) over a sorted sequence with random access — and why a linked list cannot do the fast one.

F4.03.3

Stability & sort cost

Best, average, and worst case for each sort, what stability preserves, and the Ω(n log n) lower bound on comparison sorts.

Advanced: sort once, search many — and the comparison floor

Sorting is an investment. If you will search a sequence once, a linear scan at O(n) beats paying n log n to sort it first. If you will search it many times, sorting once and then binary-searching at O(log n) each wins quickly — the break-even is only a handful of lookups. The same logic later picks a data structure: a map (F4.04) pays a hash up front to make every lookup O(1) on average, no ordering required.

There is a hard limit on the sorting half. Any sort that works only by comparing pairs of elements is, in effect, walking a decision tree whose leaves are the n! possible orderings; a binary tree with that many leaves is at least log₂(n!) ≈ n log n deep. So no comparison sort beats O(n log n) in the worst case — merge sort meets that floor, and only sorts that exploit the keys (counting, radix) can go lower. The cost dive proves it.

# one sort, then many fast searches:
sorted = Enum.sort(data)         # O(n log n), once
Search.binary(sorted, 20)     # O(log n), each lookup

# comparison-sort floor:  log2(n!) ~ n log n  (no sort beats it)

F4.02 · a balanced tree searches in O(log n)

Each comparison halves what is left to look at.

F4.03 · sort a flat sequence, then halve it too

Binary search is that same descent over a sorted array — once sorting has paid the n log n price.

Start with merge & quicksort, then linear & binary search, then stability & sort cost. Next module: F4.04 — Maps, sets & hashing, where a hash trades ordering for average-O(1) lookup.

References

Primary sources for this lesson, and where it connects in the course.

Sources

Merge sort — Wikipedia — a stable functional sort.
Cormen, Leiserson, Rivest & Stein (2022). Introduction to Algorithms (4th ed.) — sorting and searching, in depth.