Searching, Sorting & Hashing

Three topics that share one theme: each is a study of how much work is genuinely necessary, and how to avoid doing more than that.

For sorting, the answer comes from information theory. A comparison has two outcomes, so it distinguishes at most a factor of two, and distinguishing $n!$ possible orderings therefore needs at least ${\log }_{2}n!$ comparisons. That single argument gives the $\Omega (n\log n)$ lower bound and explains why every comparison sort is stuck at it.

For hashing, the answer comes from the load factor. Everything about a hash table's performance — probe counts, clustering, when to resize — is a function of how full it is, and the collision strategy only changes the constants.

The third organising fact is that a faster-than-comparison sort must not compare. Counting sort, radix sort and bucket sort all beat $n\log n$, and they do it by exploiting structure in the keys rather than by being cleverer about comparisons.

So the question to ask about any sorting algorithm is what it assumes about the data, and the question to ask about any hash table is how full it is.

1. Searching

Linear search examines elements one at a time and costs $\Theta (n)$ in the worst case, $\Theta (1)$ in the best. It requires nothing of the data, which is its only advantage.

Binary search repeatedly halves a sorted array and costs $\Theta (\log n)$.

The precondition is absolute: the array must be sorted, and applying binary search to unsorted data does not merely perform badly, it returns wrong answers.

The exact worst-case comparison count is $\lceil {\log }_2(n+1)\rceil$, because each comparison halves the remaining range and the search ends when one element remains.

Sorting to enable binary search only pays if the array is searched many times, since the sort costs $n\log n$ and each linear search costs only $n$. One search is not worth it; a thousand are.

Interpolation search guesses the position by proportion rather than always taking the midpoint, achieving $O(\log \log n)$ on uniformly distributed data and degrading to $O(n)$ when the distribution is skewed.

2. The Comparison Lower Bound

Any comparison-based sort can be drawn as a decision tree: internal nodes are comparisons, branches are outcomes, leaves are the possible orderings.

There must be at least $n!$ leaves, since every permutation of the input must be distinguishable, and a binary tree with $n!$ leaves has height at least ${\log }_{2}n!$.

By Stirling's approximation, ${\log }_{2}n!=\Theta (n\log n)$.

So no comparison-based sort can beat $\Omega (n\log n)$ in the worst case. Merge sort and heapsort achieve it, so the bound is tight and the problem is settled.

The proof also tells you exactly how to escape it: stop comparing. An algorithm that uses key values directly — as an array index, or digit by digit — is not a decision tree over comparisons and the bound does not apply.

3. The Quadratic Sorts

Three $O(n^2)$ sorts differ in ways that are examined precisely.

Selection sort always performs exactly $n(n-1)/2$ comparisons, regardless of the input, because it scans the whole unsorted region on every pass. Its compensating virtue is that it performs only $n-1$ swaps, the minimum possible, which matters when a swap is far more expensive than a comparison.

Insertion sort is $O(n)$ on already-sorted input and runs in time proportional to the number of inversions, which makes it genuinely fast on nearly-sorted data. This is why library sorts switch to it for small or almost-ordered subarrays.

Bubble sort with an early-exit flag also detects sorted input in one pass, but without the flag it is $O(n^2)$ even on sorted data — a distinction questions exploit.

Selection sort is the only one of the three that is not stable, because swapping a minimum into place can jump it past an equal element.

4. Merge Sort

Merge sort splits the array in half, sorts each half recursively, and merges.

$T(n)=2T(n/2)+\Theta (n)=\Theta (n\log n)$

The bound holds in every case — best, average and worst — because the split is always even regardless of the data.

It is stable, provided the merge takes from the left half when elements are equal, and that single implementation detail is what stability depends on.

It requires $\Theta (n)$ extra space for the merge, which is its main cost and the reason it is not used where memory is tight. In-place merging is possible but complicated and slower in practice.

Merge sort is the natural choice for linked lists, where the extra space vanishes because merging relinks nodes rather than copying them, and where quicksort's random access is unavailable.

It is also the basis of external sorting, where the data exceeds memory: sorted runs are written to disk and merged in passes.

5. Quicksort

Quicksort partitions around a pivot so that smaller elements precede it and larger follow, then recurses on each side.

The partition is the whole algorithm; there is no combine step at all, which is the mirror image of merge sort.

$T(n)=T(k)+T(n-k-1)+\Theta (n)$

where $k$ is the number of elements below the pivot.

A balanced split gives $\Theta (n\log n)$; a maximally unbalanced split gives $\Theta (n^2)$.

The worst case occurs on already-sorted input when the pivot is the first or last element, which is exactly the input a naive implementation is most likely to meet. Choosing a random pivot, or the median of three, makes the worst case vanishingly unlikely without eliminating it.

Quicksort is not stable and uses $O(\log n)$ stack space for the recursion, which is why it is usually described as in-place despite not being strictly so.

Despite the worse worst case, quicksort is usually the fastest comparison sort in practice, because its inner loop is a simple scan with excellent cache behaviour, while merge sort copies and heapsort jumps.

6. Comparing the Three

Each buys its guarantee with a different currency. Merge sort pays memory, heapsort pays cache locality, and quicksort pays worst-case certainty.

The practical resolution used by real libraries is a hybrid: quicksort by default, insertion sort below a size threshold, and a switch to heapsort if the recursion depth suggests the worst case is developing.

7. Non-Comparison Sorts

Counting sort tallies occurrences of each key value and reconstructs the array. It costs $\Theta (n+k)$ where $k$ is the range of key values, and it is stable if the output is built by scanning the input backwards.

It is only useful when $k$ is $O(n)$. Sorting a thousand values from a range of a billion would allocate a billion counters, so the range condition is not a technicality.

Radix sort sorts digit by digit, least significant first, using a stable sort at each digit. It costs $\Theta (d(n+k))$ for $d$ digits.

The inner sort must be stable, or the algorithm is simply wrong — earlier digits' ordering would be destroyed by later passes. This is the single most examined fact about radix sort.

Bucket sort distributes keys into buckets by value, sorts each bucket, and concatenates. It achieves $\Theta (n)$ average time when the keys are uniformly distributed, and degrades to the inner sort's worst case when they are not.

All three escape the comparison bound by using key values as addresses rather than comparing them, which is precisely the loophole the lower-bound proof leaves open.

8. Hashing and the Load Factor

A hash table maps a key to a slot through a hash function, giving $O(1)$ expected access.

The load factor $\alpha =n/m$ — elements divided by slots — determines everything. Both the expected probe count and the resizing policy are functions of it alone.

A good hash function distributes keys uniformly and computes quickly. The division method uses $h(k)=k\mathrm{mod}m$, and $m$ should be prime and far from a power of two, because a power of two makes the hash depend only on the low-order bits.

The multiplication method multiplies by an irrational-like constant and extracts middle bits, which is less sensitive to the choice of $m$.

Universal hashing selects a hash function at random from a family, guaranteeing good expected behaviour against any input including an adversarial one — which fixed functions cannot do.

9. Collision Resolution

Two families exist, and they behave differently as the table fills.

Separate chaining stores colliding elements in a list at the slot. The load factor may exceed 1, and the expected search cost is $\Theta (1+\alpha )$ — constant work plus a walk down a chain of average length $\alpha$.

Open addressing stores everything in the table itself, probing a sequence of slots until an empty one is found. The load factor cannot exceed 1, and performance degrades sharply as it approaches it.

Three probe sequences appear.

Linear probing checks the next slot, wrapping around. It has the best cache behaviour and the worst clustering: occupied runs merge into longer runs, and a longer run is more likely to grow, which is called primary clustering.

Quadratic probing steps by increasing squares, breaking up primary clusters but creating secondary clustering, since keys hashing to the same slot follow identical sequences.

Double hashing uses a second hash function for the step size, so keys colliding at the first slot diverge immediately. It has the best theoretical behaviour and the worst locality.

For linear probing, the expected probes for an unsuccessful search is approximately

$P_{unsucc}\approx \frac{1}{2}\left(1+\frac{1}{(1-\alpha {)}^2}\right)$

The squared term is what makes linear probing collapse near full. At $\alpha =0.9$ it predicts about 50 probes; at $\alpha =0.5$, about 2.5.

Deletion under open addressing cannot simply blank a slot, because that would break probe sequences passing through it. A deleted marker, or tombstone, is written instead, and tombstones accumulate until the table is rebuilt.

10. Worked Examples

Example 1. How many comparisons does binary search make in the worst case on 1000 elements, and how does that compare with linear search?

Each comparison halves the remaining range, so the worst case is $\lceil {\log }_2(1001)\rceil$.

Since $2^9=512$ and $2^{10}=1024$, the answer is 10 comparisons.

Linear search needs up to 1000.

The ratio is 100 to 1, and it widens: for a million elements binary search needs 20 against a million, a ratio of 50,000.

The catch is the precondition. Sorting 1000 elements costs about $1000\times 10=10,000$ comparisons, so a single search does not justify sorting. Break-even is at roughly 10 searches, and beyond that the sort pays for itself many times over.

Example 2. Prove that no comparison sort can do better than $\Omega (n\log n)$.

Model any comparison sort as a decision tree. Each internal node is a comparison between two elements, each has two children for the two outcomes, and each leaf is a permutation the algorithm can output.

For the algorithm to be correct, every one of the $n!$ possible input orderings must lead to a distinct leaf, since each requires a different rearrangement. So the tree has at least $n!$ leaves.

A binary tree of height $h$ has at most $2^h$ leaves, so $2^h\ge n!$, giving $h\ge {\log }_{2}n!$.

By Stirling's approximation, $n!\approx (n/e{)}^n\sqrt{2\pi n}$, so

${\log }_{2}n!\approx n{\log }_{2}n-n{\log }_{2}e=\Theta (n\log n)$

The height of the tree is the worst-case number of comparisons, so every comparison sort needs $\Omega (n\log n)$ comparisons on some input.

The bound is tight, since merge sort and heapsort achieve it, so nothing better exists within the comparison model. The only escape is to leave the model, which is what counting and radix sort do.

Example 3. Sort the array [170, 45, 75, 90, 802, 24, 2, 66] using radix sort, showing each pass.

Three digits are needed, since the largest value has three.

Pass 1, on the units digit: the keys sort by last digit into 170, 90, 802, 2, 24, 45, 75, 66.

Reading the units digits: 0, 0, 2, 2, 4, 5, 5, 6 — correctly ordered, with ties preserving their earlier relative order.

Pass 2, on the tens digit: starting from the pass-1 output, sort by the middle digit to get 802, 2, 24, 45, 66, 170, 75, 90.

Tens digits: 0, 0, 2, 4, 6, 7, 7, 9. Note that 170 precedes 75 because both have tens digit 7 and 170 came first in the pass-1 output — this is stability doing its work.

Pass 3, on the hundreds digit: sort by the leading digit to get 2, 24, 45, 66, 75, 90, 170, 802.

Hundreds digits: 0, 0, 0, 0, 0, 0, 1, 8. The six values with no hundreds digit keep their pass-2 order, which is already correct on the lower two digits.

The array is sorted.

The whole algorithm depends on stability. If pass 3 reordered the six zero-hundreds values arbitrarily, the work of passes 1 and 2 would be destroyed and the result would be wrong. This is why counting sort, which is stable, is the standard inner sort for radix.

Example 4. A hash table has 11 slots and uses $h(k)=k\mathrm{mod}11$ with linear probing. Insert 22, 31, 4, 15, 28, 17, 88, 59. Where does each land?

Compute each initial slot and probe forward on collision.

22 mod 11 = 0. Slot 0 is free. Placed at 0.

31 mod 11 = 9. Free. Placed at 9.

4 mod 11 = 4. Free. Placed at 4.

15 mod 11 = 4. Occupied by 15's collision with 4, so probe slot 5. Free. Placed at 5.

28 mod 11 = 6. Free. Placed at 6.

17 mod 11 = 6. Occupied, probe 7. Free. Placed at 7.

88 mod 11 = 0. Occupied by 22, probe 1. Free. Placed at 1.

59 mod 11 = 4. Occupied, probe 5 (occupied), 6 (occupied), 7 (occupied), 8. Free. Placed at 8.

The final table holds 22 at 0, 88 at 1, 4 at 4, 15 at 5, 28 at 6, 17 at 7, 59 at 8, and 31 at 9.

Notice the cluster. Slots 4 through 8 form a run of five, and 59 needed four probes to get past it. That run formed because two separate hash values, 4 and 6, produced adjacent occupied regions that merged — exactly the primary clustering that linear probing suffers from.

The load factor is 8/11, about 0.73. The linear-probing formula predicts about $\frac{1}{2}(1+1/(0.27{)}^2)\approx 7.4$ probes for an unsuccessful search, which is consistent with what the last insertion experienced.

Example 5. Why is quicksort's worst case triggered by sorted input, and why is it still preferred in practice?

With a first-element pivot on a sorted array, every element is larger than the pivot, so the partition puts zero elements on the left and $n-1$ on the right.

The recurrence becomes $T(n)=T(n-1)+\Theta (n)$, which unrolls to $n+(n-1)+\cdots +1=\Theta (n^2)$.

The recursion depth also becomes $n$ rather than $\log n$, so the stack usage becomes linear and can overflow.

The irony is that sorted or nearly-sorted input is extremely common in practice, which makes this the worst possible worst case to have.

Two fixes address it. Choosing a random pivot makes any particular input equally likely to split well, so no adversary can construct a bad case without knowing the random seed. Choosing the median of the first, middle and last elements guarantees a reasonable split on sorted input specifically, at almost no cost.

Despite all this, quicksort remains the practical default because its partition loop is a pair of sequential scans with near-perfect cache behaviour, it needs no auxiliary array, and its constant factor is markedly smaller than merge sort's. Real libraries hedge by switching to heapsort if the recursion depth exceeds about $2\log n$, which caps the worst case at $O(n\log n)$ while keeping quicksort's speed in the common case.

Example 6. A hash table with separate chaining has 1000 slots and 1500 elements. What is the expected number of comparisons for an unsuccessful search, and what changes with open addressing?

The load factor is $\alpha =1500/1000=1.5$.

For separate chaining, an unsuccessful search hashes to a slot and walks its entire chain, whose expected length is $\alpha$.

Expected comparisons: $\Theta (1+\alpha )=1+1.5=2.5$, so about 2.5 comparisons — hashing plus walking an average chain of 1.5.

A successful search walks on average half the chain, giving roughly $1+\alpha /2=1.75$.

With open addressing, this table cannot exist. Open addressing stores every element in the table itself, so the load factor cannot exceed 1, and 1500 elements will not fit in 1000 slots at all.

This is the structural difference between the two families. Chaining degrades gracefully and linearly past full, while open addressing has a hard capacity limit and degrades sharply before reaching it — at $\alpha =0.9$ linear probing already needs about 50 probes for an unsuccessful search.

The practical consequence is that open-addressed tables are resized at a load factor around 0.7, while chained tables tolerate values above 1 without difficulty.

Summary

Every sorting bound comes from information: a comparison distinguishes two cases, so separating $n!$ orderings needs ${\log }_{2}n!=\Omega (n\log n)$ comparisons, and merge sort and heapsort make that tight.

Binary search needs $\lceil {\log }_2(n+1)\rceil$ comparisons and an absolutely sorted array; sorting first pays only when the array is searched many times.

Selection sort always makes $n(n-1)/2$ comparisons but only $n-1$ swaps, and is the one quadratic sort that is not stable. Insertion sort is adaptive and linear on sorted input.

Merge sort is $n\log n$ always and stable, paying $\Theta (n)$ space. Quicksort is $n\log n$ on average and quadratic on sorted input with a naive pivot, unstable, and usually fastest in practice. Heapsort is $n\log n$ always and in place, and unstable with poor locality.

Counting sort costs $\Theta (n+k)$ and is useful only when $k$ is $O(n)$. Radix sort costs $\Theta (d(n+k))$ and requires a stable inner sort or it is simply wrong. Bucket sort is linear on uniform data.

Everything about a hash table follows from the load factor. Chaining gives $\Theta (1+\alpha )$ and tolerates $\alpha >1$; open addressing cannot exceed $\alpha =1$ and collapses well before it.

Linear probing has the best locality and suffers primary clustering; quadratic probing breaks that up but leaves secondary clustering; double hashing separates colliding keys immediately at the cost of locality.

Deletion under open addressing requires tombstones, because blanking a slot would break every probe sequence running through it.