Introduction

Non-comparison sorts can beat the O(n log n) lower bound that applies to comparison-based sorting, but only under specific assumptions about the data. They run in linear time when the key range, digit structure, or distribution keeps the extra work bounded by a constant factor of n.

Why They Can Be Faster Than Comparison Sorts

The O(n log n) lower bound applies to algorithms that learn order only by comparing elements. Counting sort, radix sort, and bucket sort avoid that model. They exploit structure in the keys instead of comparing every pair indirectly.

That advantage comes with conditions. If the structure assumptions break, the runtime can stop being linear or the algorithm may stop being a good fit entirely.

Counting Sort

Counting sort runs in O(n + k), where:

• 'n is the number of items'
• 'k is the size of the key range'

So it is linear when k = O(n) or when k is otherwise bounded tightly enough that n + k behaves like O(n) for the problem size.

Example:

1def counting_sort(values, max_key):
2    counts = [0] * (max_key + 1)
3
4    for value in values:
5        counts[value] += 1
6
7    result = []
8    for value, count in enumerate(counts):
9        result.extend([value] * count)
10
11    return result
12
13
14print(counting_sort([4, 2, 2, 8, 3, 3, 1], 8))

If max_key were enormous compared with n, the memory and runtime would no longer feel linear in practice.

Radix Sort

Radix sort runs in O(d(n + b)), where:

• 'd is the number of digits or passes'
• 'b is the base or bucket count per pass'

It is linear when d and b are bounded or small enough relative to n. In practice, that means fixed-width integers are a very good fit.

For example, sorting 32-bit integers with a fixed number of passes can be treated as linear in n because d is effectively constant for that data model.

A simple least-significant-digit example:

1def radix_sort(values):
2    exp = 1
3    result = list(values)
4
5    while max(result) // exp > 0:
6        buckets = [[] for _ in range(10)]
7        for value in result:
8            digit = (value // exp) % 10
9            buckets[digit].append(value)
10        result = [value for bucket in buckets for value in bucket]
11        exp *= 10
12
13    return result
14
15
16print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))

If the number of digits grows with input size, the runtime stops being “linear in n” in the clean constant-factor sense.

Bucket Sort

Bucket sort is often described as linear on average, not unconditionally. It works well when inputs are distributed fairly evenly across buckets and the cost of sorting within each bucket stays small.

A typical assumption is that the inputs are uniformly distributed over a known interval. Under that kind of distributional assumption, average-case runtime can be O(n).

But if many values collapse into one bucket, the per-bucket sort can dominate and the runtime can degrade badly.

The Real Conditions in Plain Language

These non-comparison sorts behave linearly under conditions like:

• key range is not much larger than the number of elements for counting sort
• digit count is fixed or bounded for radix sort
• bucket occupancy stays balanced on average for bucket sort
• extra memory requirements are acceptable

So the question is not only “which algorithm is non-comparison based,” but also “what assumptions about the keys make its extra work proportional to n.”

Common Pitfalls

The biggest mistake is quoting “linear time” without mentioning the hidden parameters such as key range, digit count, or distribution assumptions.

Another issue is treating bucket sort as guaranteed linear. It is usually average-case linear under favorable input assumptions, not worst-case linear for arbitrary data.

Developers also sometimes ignore space complexity. Counting and radix sort can be fast, but they often trade time for extra auxiliary storage.

Finally, do not use these sorts when the data lacks the structure they exploit. A comparison sort may be simpler and more appropriate when keys are large, irregular, or not easily digitized.

Summary

• Counting sort is linear when the key range k is bounded so that n + k = O(n).
• Radix sort is linear when the number of passes and bucket base stay bounded relative to n.
• Bucket sort is average-case linear when inputs distribute evenly across buckets.
• These algorithms beat comparison sorts by exploiting key structure, not by violating theory.
• Always state the extra assumptions when claiming linear time for a non-comparison sort.