Radix sort is still O(n logn). More precisely, it's O(w * n) where w is the size in bits of the data being sorted, but then it follows that w scales with log n,

Radix sort is still O(n logn). More precisely, it's O(w * n) where w is the size in bits of the data being sorted, but then it follows that w scales with log n, since n distinct items requires log n bits and hence you arrive at n logn.