4 ms·

It's probably worth noting that Radix sort is actually O(nk) with keys of length k, and that k is O(lg n) for many reasonable key representations (e.g. integers

by thurn 15y ago

It's probably worth noting that Radix sort is actually O(nk) with keys of length k, and that k is O(lg n) for many reasonable key representations (e.g. integers), giving an actual bound no better than a standard merge sort.

bartonfink 15y ago
In reasonable key representations, k would be constant and hence ignored in algorithmic analysis. In 32 bit integers, for example, 0 takes just as many bits as 2^32 - 1 and you have to compare them all each time.
- jacobolus 15y ago
  Since you sort by digit, if you're going to make your radix be the size of an integer, you'll to construct that many empty lists; in actual practical implementations of radix sort, the radix is some relatively small number, and so you end up with O(nk). I guess if you want you can say that k is actually O(log(maxint)), if all of your integers are < maxint. But that ends up being quite a sizable constant term if you really want to consider it constant. If you're going to do algorithmic analysis that entirely ignores large constants, it's a bit strange to simultaneously declare that all your integers will be bounded by some particular cutoff.
jwegan 15y ago
That is incorrect. k has no relation to n. k is the size of the range of possible values in the input and n is the actual number of elements in the input. To illustrate, consider sorting 32 bit integers. If the radix is one bit (i.e. radix=1 bit and k=2 * 32 [32 "digits" and 2 possible values for each "digit"]) then radix sort is O(64n) = O(n). Now consider, cutting up the 32-bit int into byte size chunks (i.e. radix=8 bits and k=4 * 256 [4 "digits" and 256 possible values for each "digit"]). In which that case radix sort is O(1024n). Note that we are able to determine the value of k without any idea of what n may be. In practice even for small n (n>200), a straight forward implementation of radix sort is faster than any O(nlogn) sort.

by thurn 15y ago

bartonfink 15y ago

In reasonable key representations, k would be constant and hence ignored in algorithmic analysis. In 32 bit integers, for example, 0 takes just as many bits as 2^32 - 1 and you have to compare them all each time.

jacobolus 15y ago
Since you sort by digit, if you're going to make your radix be the size of an integer, you'll to construct that many empty lists; in actual practical implementations of radix sort, the radix is some relatively small number, and so you end up with O(nk). I guess if you want you can say that k is actually O(log(maxint)), if all of your integers are < maxint. But that ends up being quite a sizable constant term if you really want to consider it constant. If you're going to do algorithmic analysis that entirely ignores large constants, it's a bit strange to simultaneously declare that all your integers will be bounded by some particular cutoff.

jwegan 15y ago

That is incorrect. k has no relation to n. k is the size of the range of possible values in the input and n is the actual number of elements in the input. To illustrate, consider sorting 32 bit integers. If the radix is one bit (i.e. radix=1 bit and k=2 * 32 [32 "digits" and 2 possible values for each "digit"]) then radix sort is O(64n) = O(n). Now consider, cutting up the 32-bit int into byte size chunks (i.e. radix=8 bits and k=4 * 256 [4 "digits" and 256 possible values for each "digit"]). In which that case radix sort is O(1024n). Note that we are able to determine the value of k without any idea of what n may be. In practice even for small n (n>200), a straight forward implementation of radix sort is faster than any O(nlogn) sort.