Chapter 2: Getting Started: Insertion Sort and Algorithm Design

Insertion sort, likened to organizing a hand of playing cards, constructs a sorted array one element at a time and is best suited for small or nearly sorted inputs, running in Θ(n) in the best case and Θ(n²) in the worst case. To formally prove its correctness, the chapter introduces loop invariants — a three-part framework of initialization, maintenance, and termination — which establishes that the subarray before each iteration remains sorted, guaranteeing a fully sorted array upon completion. Algorithm analysis is grounded in the RAM model, examining best-case, worst-case, and average-case running times, with worst-case being the primary focus, and asymptotic Θ-notation used to capture the dominant term of growth as input size scales. The chapter then introduces divide-and-conquer through merge sort, which recursively splits an array into halves, sorts each, and merges the results — yielding the recurrence T(n) = 2T(n/2) + Θ(n), which solves to Θ(n log n), making it significantly faster than insertion sort for large inputs. Throughout, the chapter employs a consistent pseudocode style drawn from common languages like C and Python, using 1-indexed arrays, dot notation for attributes, pass-by-reference semantics, and short-circuit boolean evaluation, establishing the notational conventions used across the entire book.