Sorting by Inquiry

Sorting is among the first problems a student of computing encounters and among the richest. Within it lie most of the central ideas of the analysis of algorithms: loop invariants, recurrences, expected-case analysis, adaptivity, lower bounds, and the dependence of complexity on the model of computation. Sorting by Inquiry uses this single problem as a lens through which those ideas can be studied with clarity and rigour.

Written in the tradition of inquiry-based learning, the book states its results and asks the reader to prove them. Each of its first twelve chapters is organized around a single algorithm, from selection sort and insertion sort through merge sort, heapsort, quicksort, radix sort, Shellsort, bitonic sort, and Timsort. Each chapter asks three questions: Does the algorithm work, and how can we be certain? How much work does it do, counted exactly and described asymptotically? And what idea does it carry that its predecessors did not? Readers trace every algorithm by hand before proving anything about it, so that invariants and conjectures emerge from their own computations. A central chapter proves that no comparison-based sort can make fewer than about n lg n comparisons. A substantial closing survey of more than fifty further algorithms, from comb sort and smoothsort to introsort, powersort, external and parallel sorts, and the deliberately pessimal, places each within the framework the book develops.

Features include:

• Twelve chapters, each built on one algorithm and one central idea, presented in an order in which each algorithm answers a limitation of the last
• A survey chapter covering selection, insertion, merge, partition, distribution, external, parallel, and unconventional sorting algorithms
• Precise pseudocode with numbered lines, and fully worked hand traces
• Exact counts of comparisons, exchanges, and passes alongside asymptotic analysis
• Correctness proofs through loop invariants, strong induction, and the zero-one principle
• Lower bounds by decision trees and adversary arguments
• Expected-case analysis of randomized quicksort through indicator random variables
• Discussion of open problems, including the gap sequences of Shellsort and integer sorting in linear time
• A complete notation guide
• A pen-and-paper approach requiring no programming or software

Suitable for an intermediate undergraduate course on the analysis of algorithms, for an inquiry-based seminar, or for independent study. The reader is assumed to be familiar with mathematical induction, finite sums, logarithms, and asymptotic notation.

Part of the By Inquiry series of inquiry-based mathematics texts.