[mananaysiempre]

It does, radix sort is in fact O(N) if size of the universe of values counts as a constant. It’s just slow in practice.

The definition of the machine for which the O(N log N) bound is proved is very delicate: you have to allow O(1) operations on an arbitrarily large set of values but not encoding tricks allowing multiple values to be packed into one and then manipulated unrealistically cheaply using those operations. In particular, the machine must not be able to do arbitrary arithmetic.

[Sesse__]

Or stated equivalently: The only operations allowed on elements are binary comparisons and two-element swaps, but both are O(1).

[mananaysiempre]

Kiiinda. Two-element swaps are a stretch already for merge sort, especially the O(log N)-space linked list version, let alone search trees and so on. At some point you also need to make sure you can’t sneak arbitrary computation into the (necessarily unlimited-magnitude) array index.

[nwellnhof]

A better comparison is bucket sort which is O(N) with uniformly distributed keys.

[amelius]

> if size of the universe of values counts as a constant

But of course, that is cheating.

[mananaysiempre]

I mean, it depends. In Unicode normalization you have to do a stable sort of an arbitrary number of values (code points) that can only ever map to a small finite number ( < 256) of sort keys (combining classes). Insertion sort is the best choice for ordinary inputs, but for adversarial ones a counting sort is probably your best bet.