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.
Sure, but it has the classic problems of the memory/storage required for the sort (minimum double all your keys), and a classic math issue relating to it's speed being O(k*N) and since k = number of bits/digits, N can only be as large as the number of bits/digits allow for.
This means quicksort and the like end up faster in practice for any "sort this list" operations. Radix/bucket sorting can be SUPER awesome when what you need is a single level of bucketing at all rather than exact order.
Sure, but it has the classic problems of the memory/storage required for the sort
No problem, just create a file of the necessary size on disk if you don't have enough RAM available.
Today's comment was brought to you by a large number and the letters big-O and c... where c, a large number, is the hidden constant of proportionality waiting to bite you every time you mention big-O. :-)
If we're reading from disk, then we DEFINITELY don't want radix, as then it's almost guaranteed that all time will be dominated by loading pages rather than cpu cache locality being leveraged by linear time algorithms - which is what this entire discussion is about.
If we are talking about linear in number of characters, an easy answer is building a trie and traversing it left to right. (Cache-friendly variation: https://en.wikipedia.org/wiki/Burstsort)
