[simiones]

We expect asymptotically better algorithms to be, well, asymptotically better. Even if they lose out for small N, they should win for larger N - and we typically expect this "larger N" to not be that large - just big enough so that data doesn't fit in any cache or something like that.

However, in this particular case, the higher-complexity sorting algorithms gets better than the hash algorithm as N gets larger, even up to pretty large values of N. This is the counter-intuitive part. No one is surprised if an O(n log n) algorithm beats an O(n) algorithm for n = 10. But if the O(n log n) algorithm wins for n = 10 000 000, that's quite surprising.

[swiftcoder]

As others have likely pointed out by now, radix sort is not O(n log n).

It's O(k * n), where k is constant with respect to the key size.

For 64-bit keys with 1024 buckets, k==8, so it's O(8 * n) = O(n)