Non-Comparison Sorts
[!NOTE] This module explores the core principles of Non-Comparison Sorts, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.
1. The Hook: Breaking the Speed Limit
We proved that any comparison-based sort needs Ω(N log N) comparisons. But what if we don’t compare elements? What if we use their value to determine their address?
If we have information about the range of the data (e.g., integers from 0 to 100), we can sort in O(N).
2. Counting Sort
Constraint: Integers in a small range [min, max].
Idea: Make an array count of size max - min + 1.
- Traverse input, increment
count[input[i] - min]. - Traverse
countarray, calculate prefix sums to find starting positions. - Place elements into output array.
Complexity: O(N + K) where K is the range. Trap: If K is huge (109) and N is small, this crashes memory.
3. Radix Sort
Constraint: Integers or fixed-length strings. Idea: Use Counting Sort as a subroutine.
- Sort by the Least Significant Digit (1s place).
- Sort by the 10s place.
- …
- Sort by the Most Significant Digit.
Wait, why LSD first? Because the sort must be Stable. When we sort by 10s column, the order relative to the 1s column must remain preserved if the 10s are equal.
Complexity: O(d ⋅ (N + b)) where d is digits and b is base (10). Basically O(N) for fixed-width integers.
4. Implementation: Radix Sort (Java)
// Main function to do Radix Sort
public void radixSort(int[] arr) {
int max = getMax(arr);
// Apply counting sort to each digit place
for (int exp = 1; max / exp > 0; exp *= 10) {
countSort(arr, exp);
}
}
private void countSort(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10]; // Base 10
// Store count of occurrences
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
// Change count[i] so that it contains position of digit
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// Build the output array (Go backwards for Stability!)
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// Copy output array to arr
System.arraycopy(output, 0, arr, 0, n);
}
5. Hardware Reality: Random Access Penalty
Counting sort looks fast (O(N)), but it involves Random Write Memory Access.
count[arr[i]]++ jumps to a random location in the count array.
If the count array fits in L1 Cache, it’s blazing fast.
If the count array is large (e.g., sorting 64-bit integers by 16-bit chunks), it causes Cache Thrashing.