Chapter 8: Sorting in Linear Time | Introduction to Algorithms (Podcast Summary)

Chapter 8 explores sorting algorithms that can run in linear time, breaking past the traditional Omega(n log n) lower bound for comparison-based sorting by making assumptions about the input. It introduces three non-comparison sorts — counting sort, radix sort, and bucket sort — and explains how each leverages structure in the input domain to achieve fast performance.

✅ Comparison Sorts and Decision Tree Lower Bound
🔸 Merge sort, heapsort, and quicksort rely on element-to-element comparisons
🔸 Decision trees represent comparison operations in sorting
🔸 Tree with n! leaves (one per permutation) → height is Omega(n log n)
🔸 Theorem 8.1: Every comparison sort has worst-case time Omega(n log n)
🔸 Merge sort and heapsort are asymptotically optimal comparison sorts

✅ Counting Sort
🔸 Assumes input integers in range 0 to k
🔸 Uses auxiliary array C[0 to k] for counting occurrences
🔸 Steps:
 🔸 Count occurrences
 🔸 Accumulate counts
 🔸 Place elements in correct position in output array
🔸 Time complexity: Theta(n + k)
🔸 Stable sort — maintains original order of equal elements
🔸 Ideal when k = O(n)

✅ Radix Sort
🔸 Sorts d-digit numbers by processing one digit at a time
🔸 Uses stable sort (like counting sort) on each digit from least to most significant
🔸 Time complexity: Theta(d(n + k))
🔸 b-bit numbers treated as d = ceil(b/r) digits of r bits
🔸 When d is constant and k = O(n), radix sort runs in linear time
🔸 Choice of digit size r affects performance
🔸 Can outperform comparison-based sorts when input has fixed digit structure

✅ Bucket Sort
🔸 Assumes input drawn from uniform distribution over [0, 1)
🔸 Steps:
 🔸 Create n buckets
 🔸 Distribute input into buckets based on value
 🔸 Sort each bucket (typically with insertion sort)
 🔸 Concatenate buckets
🔸 Average-case time: O(n)
🔸 Worst-case time: Theta(n²) if all elements fall into one bucket
🔸 With well-distributed input, expected bucket sizes stay small
🔸 Using O(n log n) sort per bucket gives better worst-case performance

✅ Design Insights and Stability Considerations
🔸 Stability is important for radix sort (depends on stability in digit-level sorts)
🔸 Counting sort is stable by design
🔸 Bucket sort’s performance depends on input distribution
🔸 Non-comparison sorts are input-sensitive: they exploit domain structure

📚 Glossary of Key Terms
🔸 Comparison Sort – Sorts by comparing elements (e.g., quicksort, mergesort)
🔸 Counting Sort – Linear-time sort for integers in a limited range
🔸 Radix Sort – Digit-wise stable sort, efficient for fixed-length numbers
🔸 Bucket Sort – Uniform-distribution-based sort using multiple buckets
🔸 Decision Tree – Binary tree representing comparison operations
🔸 Omega(n log n) – Lower bound for comparison sorts
🔸 Stable Sort – Maintains relative order of equal elements
🔸 In-place Sorting – Uses only constant extra memory
🔸 Uniform Distribution – All values equally likely within range
🔸 Oblivious Compare-Exchange – Fixed sequence of comparisons, independent of data
🔸 0–1 Sorting Lemma – If an oblivious algorithm can sort 0s and 1s, it works for all inputs
🔸 Columnsort – Oblivious sorting algorithm using matrix transformations
🔸 k-Sorted Array – For all valid i, A[i] ≤ A[i+k]