Sorting in Linear Time — Counting Sort, Radix Sort, and Bucket Sort Explained | Chapter 8 of Intro to Algorithms

While traditional comparison-based sorts like quicksort and mergesort are limited by a lower bound of Ω(n log n), Chapter 8 of introduction to algorithms introduces a set of ingenious algorithms that can sort in linear time under specific conditions. By making assumptions about the input domain or distribution, counting sort, radix sort, and bucket sort break the speed barrier of comparison sorts and become essential tools for specialized high-performance applications.

Want a clear audio breakdown? Watch the chapter summary below, and subscribe to Last Minute Lecture for more practical, podcast-style guides to every chapter of introduction to algorithms.

Why Comparison Sorts Hit a Limit

Comparison sorts like merge sort, heapsort, and quicksort fundamentally rely on comparing elements to determine order. Decision trees, which model these comparisons, must have at least n! leaves (one for each permutation), leading to a minimum height—and therefore a worst-case running time—of Ω(n log n). Theorem 8.1 confirms that all comparison sorts share this lower bound, making them asymptotically optimal within their class.

Counting Sort: Harnessing Integer Ranges

Counting sort sidesteps comparisons by assuming the input elements are integers within a fixed range 0 to k. The algorithm uses an auxiliary array to count occurrences, accumulates counts, and then places each input element directly in its output position. This results in a stable sort with time complexity Θ(n + k), ideal when k = O(n). Counting sort is widely used as a subroutine in other linear-time sorts due to its efficiency and stability.

Radix Sort: Sorting by Digits

Radix sort sorts numbers by processing individual digits, starting from the least significant. Each pass uses a stable sort (typically counting sort) to order the input based on a single digit. For d-digit numbers where each digit has k possible values, radix sort runs in Θ(d(n + k)) time. By choosing appropriate digit sizes and exploiting stability, radix sort can outperform comparison-based sorts on fixed-length numbers, especially when d is small and k = O(n).

Bucket Sort: Sorting Uniform Distributions

Bucket sort is designed for inputs drawn uniformly from the interval [0, 1). The algorithm divides the range into n buckets, distributes input values into these buckets, sorts each bucket (often with insertion sort), and concatenates the results. With uniformly distributed inputs, the expected bucket size remains small, and the average-case running time is O(n). However, worst-case performance is Θ(n²) if all elements fall into a single bucket, so input distribution is critical.

Design Insights: Stability and Input Sensitivity

• Stability is crucial for radix sort (depends on underlying digit sort) and is inherent in counting sort.
• Bucket sort depends on the uniformity of input distribution for linear time performance.
• Non-comparison sorts exploit domain structure—when input is known to have specific characteristics, these methods can outperform traditional sorting algorithms by a wide margin.

Key Concepts and Glossary

• Comparison Sort: Any sort based solely on comparing elements (e.g., quicksort, mergesort)
• Counting Sort: Linear-time sort for integers in a limited range
• Radix Sort: Digit-wise stable sort for fixed-length numbers
• Bucket Sort: Sort for uniformly distributed values using multiple buckets
• Decision Tree: Binary tree representing sorting by comparisons
• Stable Sort: Maintains order of equal elements
• Uniform Distribution: All values equally likely within the input range
• Oblivious Compare-Exchange: Fixed sequence of comparisons, independent of input
• 0–1 Sorting Lemma: Principle about oblivious sorting algorithms
• k-Sorted Array: Array where each element is at most k positions from its sorted place

Conclusion: Choosing the Right Sort for the Job

Chapter 8 of introduction to algorithms demonstrates that when you can leverage knowledge of the input domain, you can dramatically accelerate sorting with non-comparison algorithms. Counting sort, radix sort, and bucket sort have become standards in high-performance computing, especially in domains where input properties are well defined. Selecting the right sorting approach can mean the difference between sluggish performance and lightning-fast results.

Ready to dive deeper? Watch the full chapter summary on YouTube and explore more textbook breakdowns on Last Minute Lecture.

Don’t miss upcoming episodes—subscribe for clear, chapter-by-chapter walkthroughs of introduction to algorithms and beyond!

If you found this breakdown helpful, be sure to subscribe to Last Minute Lecture for more chapter-by-chapter textbook summaries and academic study guides.