Non-comparison sorts
Overview
Algorithms like Counting Sort, Bucket Sort, and Radix Sort that sort data without comparing elements against each other.
To beat the O(n log n) time barrier and sort in O(n) time when data properties (like small integer ranges) allow it.
Where used: Sorting integers in a known small range, Suffix array construction, Sorting strings by length or character
Why it exists
Problem: Comparison-based sorts like Merge Sort and Quick Sort have a theoretical lower bound of O(n log n). We cannot sort faster if we rely purely on comparing elements a <= b.
Naive approach: Use a comparison sort, accepting O(n log n) as the speed limit.
Better idea: If we know something about the data (e.g., it only contains integers from 0 to 100), we can skip comparisons altogether and just count occurrences or place items into buckets, achieving O(n) time.
Why learn this
- To understand the fundamental limits of comparison sorting.
- To know when O(n) sorting is possible in interviews.
- To learn how to use frequency arrays for more than just counting.
Mental model
Instead of weighing items against each other, just tally how many of each item exist and write them out in order.
Counting sort creates a frequency array (histogram) where the index represents the value and the array holds the count. Radix sort groups numbers by individual digits, sorting them digit-by-digit from least to most significant.
Repeated decision: For each element, what bucket or count tally does this value belong in?
Deep dive
The mathematical limit for any sorting algorithm that only uses `<` or `>` comparisons is `O(n log n)`. To break this limit, we have to cheat. We 'cheat' by using the values themselves as direct memory addresses or indices.
In **Counting Sort**, if we know all numbers are between `0` and `k`, we create an array of size `k + 1`. We iterate through our data, incrementing the count at index `x` for each number `x`. Finally, we walk through the frequency array from `0` to `k` and output the values. The time complexity is `O(n + k)`. If `k` is small, this is effectively `O(n)`. However, if the range `k` is a billion, we would waste a billion memory slots, making it impractical.
**Radix Sort** solves the memory problem for large integers. Instead of one giant counting sort, it does several small counting sorts—one for each digit. By sorting all numbers by their 1s digit, then 10s digit, then 100s digit (using a stable sort like Counting Sort), the entire array becomes sorted. The time complexity is `O(d * (n + b))` where `d` is the number of digits and `b` is the base (e.g., 10).
Both algorithms trade space for time. They require `O(n)` extra space (or `O(n + k)` for Counting Sort) and are typically not done in-place.
Key points
- Complexity: Time is O(n + k) for Counting Sort. Space is O(n + k). For Radix Sort, Time is O(d * (n + b)).
- Stability is Required: Radix sort only works if the underlying sort (usually Counting Sort) is stable, meaning it preserves the relative order of equal keys.
Pattern: Frequency array sorting
Recognition cues:
- Sort an array in O(n) time
- Elements are bounded in a small range 1 to 100
- Sorting colors or categorical data
Failure signals
- The range of numbers is very large compared to `n`.
- The data consists of floating point numbers or complex objects.
Engineering examples
Suffix Arrays
Sorting a massive number of string suffixes for text search algorithms.
Radix sort is used to sort string prefixes in O(n) time, crucial for fast suffix array construction.
When not to use
- Sorting floats or arbitrary objects: These algorithms rely on discrete integer keys. They don't easily adapt to objects without an integer mapping.
Common mistakes
- Using it on large ranges: Using Counting Sort when the input is `[1, 1000000000]` will allocate a massive array for just two elements, wasting space and time.
- Negative numbers: Basic Counting Sort uses values as array indices, so negative numbers will cause out-of-bounds errors. You must offset all values by the minimum element to make them non-negative.
Recall questions
- What is the time complexity of Counting Sort?
- Why does Radix Sort require a stable subroutine?
- Why don't we always use Counting Sort?
Understanding checks
If you use Counting Sort on the array `[3, 1, 3, 2]`, what is the frequency array generated?
It is `[0, 1, 1, 2]` (index 0 has 0, index 1 has 1, index 2 has 1, index 3 has 2).
The frequency array records how many times each value appears in the input.
What happens if you run Counting Sort on an array containing negative numbers without offsetting them?
The program will crash or behave unexpectedly due to negative array indexing.
Counting Sort uses the element values directly as array indices. Negative indices are invalid or access elements from the back of the array.
Questions & answers
Sort an array of colors represented by 0, 1, and 2 in O(n) time.
Use counting sort (or the Dutch National Flag algorithm) since the range is exactly 3.
Approach: Count the occurrences of 0, 1, and 2, then overwrite the array with that many 0s, 1s, and 2s.
Given an array of n integers between 1 and n, find the duplicate number in linear time.
Because the range is small and bounded by n, we can use the array itself as a frequency table (often by negating values at the index corresponding to each number).
Approach: Recognize that small ranges allow elements to act as their own keys.
Practice tasks
Sort Colors
Given an array `nums` with n objects colored red, white, or blue (represented as 0, 1, 2), sort them in-place so that objects of the same color are adjacent. Can you do this in O(n) using counting?
Continue learning
Previous: Big-O Notation