13.2 Non-Comparison Sorting Algorithms

Non-Comparison Sorting Algorithms

Non-comparison sorting algorithms take a fundamentally different approach from algorithms like merge sort or quicksort. Instead of deciding order by comparing pairs of elements, they exploit the structure of the data itself (its digits, its value range, its distribution) to place elements directly into their correct positions. This lets them break through the $O(n \log n)$ lower bound that applies to all comparison-based sorts, achieving linear time in favorable conditions.

These algorithms work best on integer arrays or data that can be mapped to integers within a known range. Understanding when and why they outperform comparison sorts is the core takeaway of this section.

Principles of Non-Comparison Sorting

Counting Sort works by tallying how many times each value appears, then using those counts to compute where each element belongs in the output.

• Assumes input elements are integers in a specific range $[0, k]$
• Builds a histogram: a count array where index $i$ stores how many times value $i$ appears
• Transforms the count array into a prefix sum array, so each entry tells you how many elements are less than or equal to that value
• Uses the prefix sums to place each element directly into its correct output position, with no comparisons needed
• Works well when the range $k$ is small relative to $n$ (e.g., exam scores 0–100, ages 0–120)

Radix Sort sorts numbers digit by digit, starting from the least significant digit and working toward the most significant.

• Each pass sorts the array by one digit position using a stable subroutine (typically counting sort). Stability is critical here: it preserves the ordering established by previous passes, so earlier digit sorts aren't undone.
• After processing all $d$ digit positions, the array is fully sorted.
• Particularly effective for fixed-width data like zip codes, phone numbers, or fixed-length strings.

Bucket Sort distributes elements across a set of "buckets" that each cover a subrange of the input, sorts each bucket individually, then concatenates the results.

• Each bucket represents a subinterval of the input range (e.g., prices $[0, 10)$, $[10, 20)$, etc.)
• Elements are assigned to buckets based on their value, grouping similar values together
• Each bucket is sorted independently, often with insertion sort (which is fast on small or nearly-sorted data)
• The sorted buckets are concatenated in order to produce the final output
• Performs best when input is uniformly distributed over the range (e.g., floating-point numbers between 0 and 1), because that keeps bucket sizes roughly equal

Implementation for Integer Arrays

Counting Sort Implementation

1. Find the maximum value $k$ in the input array.

2. Create a count array of size $k + 1$, initialized to zero.

3. Iterate through the input array and increment count[element] for each element.

4. Compute the prefix sum of the count array: each entry now stores the number of elements less than or equal to that index. This tells you the last valid position for that value in the output.

5. Build the sorted output array by traversing the input in reverse order (this preserves stability). For each element, place it at position count[element] - 1 in the output, then decrement that count.

6. Copy the output array back to the original array.

Radix Sort Implementation

1. Find the maximum element and determine how many digits $d$ it has.

2. For each digit position, starting from the least significant:

   • Run counting sort on the array using only the current digit as the key (extract the digit with division and modulo operations).
   • Because counting sort is stable, the relative order from previous passes is preserved.

3. After all $d$ passes, the array is sorted.

Bucket Sort Implementation

1. Choose the number of buckets. A common choice is $n$ buckets for $n$ elements, though $\sqrt{n}$ is also used.
2. Determine the range of the input and assign each element to a bucket based on its value (e.g., bucket_index = floor(n * element / max_value)).
3. Sort each bucket individually using a simple algorithm like insertion sort.
4. Concatenate all buckets in order to produce the final sorted array.

Complexity of Non-Comparison Algorithms

Counting Sort

• Time: $O(n + k)$, where $n$ is the number of elements and $k$ is the range of input values. You iterate through the input once and through the count array once.
• Space: $O(n + k)$ for the count array (size $k + 1$) and the output array (size $n$).
• The catch: if $k$ is much larger than $n$, this becomes wasteful. Sorting 10 elements in the range $[0, 1{,}000{,}000]$ means allocating a million-entry count array.

Radix Sort

• Time: $O(d \cdot (n + k))$, where $d$ is the number of digits and $k$ is the radix (base). For decimal digits, $k = 10$; for bytes, $k = 256$.
• Space: $O(n + k)$ for the counting sort subroutine's temporary arrays.
• Since $d$ and $k$ are often treated as constants (e.g., sorting 32-bit integers in base 256 gives $d = 4$, $k = 256$), radix sort effectively runs in $O(n)$ for fixed-width data.

Bucket Sort

• Time: $O(n + k)$ on average, where $k$ is the number of buckets. This average case assumes uniform distribution, which keeps each bucket at roughly $O(1)$ elements. More precisely, sorting bucket $i$ takes $O(n_i \log n_i)$ if using a comparison sort, but with uniform distribution and $k = n$ buckets, each $n_i$ is $O(1)$.
• Worst case: $O(n^2)$ if all elements land in the same bucket and you're using insertion sort inside it.
• Space: $O(n + k)$ for the bucket structures and output.

Non-Comparison vs. Comparison-Based Sorting

Advantages

• Can achieve $O(n)$ time (or close to it), beating the $O(n \log n)$ lower bound that applies to all comparison-based sorts
• Counting sort is extremely fast when the value range $k$ is small relative to $n$
• Radix sort handles large datasets of fixed-width integers or strings very efficiently
• Counting sort and radix sort are stable, which matters when you need to preserve the relative order of equal elements

Limitations

• You need to know (or compute) the range of input values ahead of time
• Higher space complexity than in-place comparison sorts like heapsort or quicksort, since they require auxiliary arrays or bucket structures
• Not directly applicable to arbitrary data types (floats, objects with custom orderings) without first mapping values to integers
• Performance degrades badly when $k \gg n$: counting sort wastes space, and bucket sort produces unbalanced buckets
• None of these algorithms sort in-place in the traditional sense, which can be a constraint in memory-limited environments