3 ms·

Incidentally, the sorting algorithm described here is a counting sort: http://en.wikipedia.org/wiki/Counting_sort http://en.wikipedia.org/wiki/Counting_sort W

by pjscott 16y ago

Incidentally, the sorting algorithm described here is a counting sort: http://en.wikipedia.org/wiki/Counting_sort http://en.wikipedia.org/wiki/Counting_sort When you're trying to get nice low asymptotic time bounds on things, it can really help to remember counting sort, radix sort, and tries. Counting and radix sort are O(n), and tries are a really handy data structure with the same worst-case asymptotic time as the expected amortized time of hash tables. They also support in-order key traversal and prefix/range queries.

thurn 16y 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 16y 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 16y 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 16y 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 pjscott 16y ago

thurn 16y 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 16y 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 16y 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 16y 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.