4 ms·

Radix Sort Revisited

• cperciva 16y ago
  [Radix sort] breaks the theoretical lower bound of the O(NlogN) complexity, which only applies for comparison-based sorts. Radix is O(kN), with k = 4 most of the time Sigh. In fact, radix sort is O(k*N) with k = log N. There's nothing magical about it. More precisely, radix sort is O(N log U) where U is the number of distinct values the inputs can take (e.g., U = 2^32 for 32-bit integers) while comparison sorts are O(N log R) where R is the number of distinct input values (e.g., R = N if the values to be sorted are distinct). Radix sorts often win due to being easy to implement efficiently, but they have the same or worse asymptotic behaviour.
  • ssp 16y ago
    If you are going to say that there really are log n bits in a word, then you also need to account for the time it takes to actually do a comparison, which would be Omega(log n) in the worst case because you can't describe n values with less than log n bits -- making comparison sort Omega (n log^2 n)
    • cperciva 16y ago
      You don't need to compare all the bits in a word -- you just need to find the first place where two values differ.
      • ssp 16y ago
        It isn't obvious to me that that is enough to guarantee amortized constant time.
      • SamReidHughes 16y ago
        The length of the common prefix generally grows linearly from 1 to O(log(n)) on randomly distributed values (and worse on less-randomly distributed values) -- if you follow a given value, it starts off being compared against another random value, then against a value with probably one bit in common, then against a value with probably two bits in common, and so on, until O(log(n)) comparisons have been done.
  • deleted 16y ago
    [deleted]