5 ms·

http://en.wikipedia.org/wiki/Radix_sort http://en.wikipedia.org/wiki/Radix_sort

• Yrlec 17y ago
  Radix-sort is actually not linear. The algorithm will only work if the word-length w>=log(n) (because otherwise you can't store all possible n) so O(nw) is practically the same thing as O(nlog(n))
  • tybris 17y ago
    Not sure what you mean by storing all possible n. Radix sort is O(nw) and for most use-cases w is smaller than log(n).
    • Yrlec 17y ago
      A word which is w bits long can hold a number between 0 and 2^w-1. If you want to hold a larger interval than that you need to increase the size of w. Perhaps you can make it smaller than log(n) for many use cases by restricting the type of input you accept but O(f(x)) only refers to the worse case.
  • pmjordan 17y ago
    That's certainly true in general, but by choosing a fixed-length word size (i.e. 16, 32 or 64 bit integers) you can preselect w so that runtime is predictably O(n). I can't see a way of doing that with most other O(n log(n)) sorting algorithms. Additionally, the constant factor is typically low compared to other algorithms.
    • Yrlec 17y ago
      Restricting the size of w (and therefore also n) does not make it linear. Lets say you have restricted w to 32. Then you also know that n <= 2^32. If you now for instance are using mergesort then you also know that the number of recursions are at most 32 (since you split the input in half each time), i.e. it executes within at most 32n operations. So with that logic mergesort would also be linear.
      • pmjordan 17y ago
        No, in the merge sort example it's not 32n operations, but a maximum of 32 levels of splits, but the number of comparisons, which dominate runtime, is still k * n * log(n). Not so for radix sort, because there are no direct comparisons. By choosing a word length in advance (often hard-coded) the number of items to sort affects the runtime linearly.
        • Yrlec 17y ago
          I think you are mixing runtime scalability with the actual complexity. Big-O definition from Wikipedia: Let f(x) and g(x) be two functions defined on some subset of the real numbers. One writes f(x) = O(g(x)) as x -> infinity if and only if, for sufficiently large values of x, f(x) is at most a constant times g(x) in absolute value. That is, f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x0 such that |f(x)| <= M|g(x)| for all x > x0. In the above case M = 32, f = mergesort and g(x) = x because no matter of large input you have mergesort will always take less than or equal to 32n operations (since log(n)<=32) .