3 ms·

Radix sort exists

• tshaddox 6y ago
  Good luck using that for a big list of strings!
  • lomereiter 6y ago
    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 https://en.wikipedia.org/wiki/Burstsort)
• codemac 6y ago
  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.
  • Silhouette 6y ago
    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. :-)
    • codemac 6y ago
      Huh? 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.
      • higerordermap 6y ago
        He was sarcastic
• Kranar 6y ago
  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.