Sorting and Searching — Skiena, Chapter 4

Chapter 0: Why Sort?

Sorting is the most fundamental algorithmic problem in computer science. Not because sorting itself is so exciting, but because so many other problems become easy once the data is sorted.

Need to find duplicates? Sort the data -- duplicates become neighbors. Need the median? Sort the data -- it's the middle element. Need to find the closest pair of numbers? Sort first -- the answer must be adjacent elements.

Skiena's take-home lesson: Sorting lies at the heart of many algorithms. Sorting the data is one of the first things any algorithm designer should try in the quest for efficiency.

Consider the problem of testing whether two sets are disjoint (share no elements). Without sorting, you must compare every element of set A against every element of set B: O(nm) time. But if you sort the smaller set first, you can binary-search for each element of the larger set: O((n+m) log m) time. For large inputs, that's the difference between hours and seconds.

The library sort function in your programming language is one of the most useful tools you have. Use it freely. But understanding how the major sorting algorithms work teaches design techniques that apply far beyond sorting.

Why is sorting often the first step in solving a different problem?

Because sorted data enables binary search, duplicate detection, and neighbor-based queries, making many problems much easier Because sorted data uses less memory Because it's required by the programming language

Chapter 1: Selection Sort

The simplest sorting algorithm is selection sort: repeatedly find the minimum element from the unsorted portion and put it next in the sorted output.

Find minimum

Scan the unsorted portion for the smallest element.

↓

Swap to front

Swap it with the first unsorted element.

↻ repeat until sorted

Selection sort does n iterations. On each iteration, it scans the remaining unsorted elements to find the minimum. The first scan looks at n elements, the second at n-1, then n-2, and so on. The total number of comparisons is:

n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²)

Can we do better? The bottleneck is finding the minimum -- it takes O(n) per iteration because we use an unsorted array. But Chapter 3 gave us a data structure that finds the minimum in O(log n) time: the heap. Replacing the unsorted array with a heap immediately improves selection sort from O(n²) to O(n log n). That improved algorithm has a name: heapsort.

The lesson: Selection sort is not just a slow algorithm to discard. It reveals a design pattern: the right data structure can turn a slow algorithm into a fast one. Heapsort IS selection sort with a better data structure.

What makes selection sort O(n²)?

Finding the minimum takes O(n) per iteration, and there are n iterations Swapping elements is expensive It uses too much memory

Chapter 2: Heapsort

A heap is a binary tree stored in an array where every parent dominates its children (smaller in a min-heap, larger in a max-heap). The key property: the minimum is always at the root, accessible in O(1).

The array trick is elegant. For element at position k:

parent(k) = ⌊k/2⌋, left-child(k) = 2k, right-child(k) = 2k + 1

Heapsort works in two phases. First, build a heap from the unsorted data (O(n) time using bottom-up construction). Then, repeatedly extract the minimum (O(log n) each), producing elements in sorted order.

Heap Extract-Min

Click "Extract Min" to remove the root and watch the heap repair itself by bubbling down. The sorted output grows on the right.

Total cost: O(n) to build the heap + O(n log n) for n extractions = O(n log n). Heapsort is guaranteed O(n log n) in the worst case, with no extra memory beyond the array itself.

Why does extracting the minimum from a heap take O(log n)?

Because you must search the whole heap Because the replacement element must bubble down through O(log n) levels of the tree Because you must rebuild the entire heap

Chapter 3: Mergesort

Mergesort is the classic divide-and-conquer sorting algorithm. The idea is beautifully simple:

Divide

Split the array into two halves.

↓

Conquer

Recursively sort each half.

↓

Merge

Combine the two sorted halves into one sorted array.

The merge step is the key. Given two sorted arrays, we can merge them into one sorted array in O(n) time by repeatedly taking the smaller of the two front elements.

How many levels of recursion are there? Each level halves the array, so there are log₂ n levels. Each level does O(n) total work (merging). Therefore the total is:

O(n) × O(log n) = O(n log n)

Mergesort vs heapsort: Both are O(n log n) worst case. Mergesort has excellent cache behavior (sequential access) and is stable (equal elements keep their original order). The downside: mergesort needs O(n) extra space for the merge buffer. Heapsort is in-place but has poor cache locality due to the tree jumps.

Mergesort Visualization

Watch the array split, sort recursively, and merge back together. Each row shows a level of the recursion.

Ready

Why does mergesort take O(n log n) time?

There are log n levels of recursion, and each level does O(n) work merging It does n comparisons per element It's the same as selection sort but faster

Chapter 4: Quicksort

Quicksort is the most widely used sorting algorithm in practice. Like mergesort it divides and conquers, but with a twist: the hard work happens during the divide, not the merge.

Pick a pivot

Choose an element p from the array.

↓

Partition

Move elements < p to the left, elements > p to the right.

↓

Recurse

Recursively sort the left and right partitions.

After partitioning, the pivot is in its final sorted position. No merge step is needed -- the array is sorted in place.

The pivot matters: If the pivot splits the array roughly in half each time, quicksort is O(n log n). But if the pivot is always the smallest or largest element (as happens with sorted input and a first-element pivot), the partitions are maximally unbalanced and quicksort degrades to O(n²). Solution: pick the pivot randomly. A random pivot gives expected O(n log n) regardless of input.

Despite the O(n²) worst case, quicksort is typically 2-3x faster than mergesort in practice. Why? The inner loop (partition step) has excellent cache locality, fewer data movements, and a very small constant factor. That's why most library sort functions use quicksort (or a hybrid like introsort).

When does quicksort degrade to O(n²)?

When the array has duplicates When the pivot consistently creates maximally unbalanced partitions (e.g., always the smallest element) When the array is too large

Chapter 5: Binary Search

Binary search is the key algorithm that makes sorted data powerful. Given a sorted array, we can find any element in O(log n) time by repeatedly halving the search space.

Compare with middle

Is the target equal to, less than, or greater than the middle element?

↓

Eliminate half

If less, search the left half. If greater, search the right half.

↻ repeat until found or empty

Each comparison eliminates half the remaining elements. After k comparisons, only n/2^k elements remain. We're done when n/2^k = 1, which gives k = log₂ n.

Binary Search

Watch binary search find the target value. Each step highlights the remaining search space and the comparison.

Ready

Binary search beyond arrays: The principle of "halving the search space" extends far beyond sorted arrays. You can binary-search on the answer to any monotonic function: "What's the smallest x such that f(x) ≥ target?" This technique appears in optimization, numerical methods, and competitive programming constantly.

How many comparisons does binary search need on a sorted array of 1 million elements?

About 20 (log₂(1,000,000) ≈ 20) About 1000 About 500,000 (half the array)

Chapter 6: The n log n Barrier

Heapsort, mergesort, and quicksort all achieve O(n log n). Is this optimal, or could a sorting algorithm do better?

The answer is: no comparison-based sorting algorithm can do better than O(n log n). Here's the argument. A comparison sort can only learn about the order of elements by comparing pairs. With n elements, there are n! possible orderings. Each comparison has two outcomes (yes/no), so after k comparisons we can distinguish at most 2^k orderings. To distinguish all n! orderings, we need:

2^k ≥ n! ⇒ k ≥ log₂(n!) = Θ(n log n)

This is an information-theoretic lower bound. No cleverness in algorithm design can circumvent it, because the information simply isn't there in fewer comparisons.

Non-comparison sorts: The O(n log n) barrier only applies to comparison-based sorts. If we know the keys are integers in a bounded range, algorithms like counting sort, radix sort, and bucket sort can achieve O(n) time by exploiting the structure of the keys directly, bypassing comparisons entirely.

Algorithm	Best	Average	Worst	Space	Stable?
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No
Heapsort	O(n log n)	O(n log n)	O(n log n)	O(1)	No
Mergesort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quicksort	O(n log n)	O(n log n)	O(n²)	O(log n)	No

Why can't a comparison-based sorting algorithm beat O(n log n)?

Because distinguishing n! possible orderings requires at least log₂(n!) = Θ(n log n) binary comparisons Because computers are not fast enough Because no one has tried hard enough

Chapter 7: The Sort Race

Let's watch three sorting algorithms compete in real time. Each algorithm sorts the same random array while you watch the comparisons and swaps happen.

Sorting Algorithm Race

Click "Race!" to sort a random array with three algorithms simultaneously. Watch the bar heights converge to sorted order. The counter shows comparisons made.

n 30

What to notice: Selection sort moves methodically left-to-right, building the sorted portion one element at a time -- visibly slow. Mergesort works in recursive waves -- small sorted chunks merge into larger ones. Quicksort works chaotically at first but converges quickly. Watch the comparison counters: selection sort uses roughly n²/2 comparisons, while mergesort and quicksort use roughly n log n.

After racing the algorithms on n=50, which has the most comparisons?

Selection sort (~1225 comparisons, roughly n²/2) Mergesort They all use the same number

Chapter 8: Connections

Sorting and searching are foundational tools that appear throughout the rest of the book. Here is where they connect:

Concept	Where It Leads
Binary search	Used in Chapter 6 for edge selection, Chapter 9 for decision problems
Heaps	Chapter 6: Priority queues power Prim's and Dijkstra's algorithms
Divide-and-conquer	The pattern behind mergesort reappears in algorithms for closest pair, matrix multiplication, and FFT
Randomization	Quicksort's random pivot idea extends to randomized algorithms throughout Chapter 7
The n log n barrier	Chapter 9: Lower bounds and impossibility results via reduction

Skiena's take-home lessons from Chapter 4:
• Sorting is the most fundamental operation in algorithm design. When in doubt, sort first.
• Heapsort = selection sort + the right data structure. This pattern (improving algorithms by improving data structures) recurs throughout CS.
• Quicksort is O(n²) worst case but O(n log n) expected with random pivots, and fastest in practice due to cache locality.
• The O(n log n) comparison-sort barrier is information-theoretic: you cannot distinguish n! orderings with fewer than log₂(n!) comparisons.
• Binary search is the most important idea: halving the search space gives O(log n) queries on sorted data.

You need a guaranteed O(n log n) in-place sort. Which algorithm?

Mergesort (requires O(n) extra space) Heapsort (O(n log n) worst case, O(1) extra space) Quicksort (O(n²) worst case)