3 ms·
nit: runtime for radix sort is O(nk), since you sort the full list by each of the digits, sequentially. I've always thought claiming radix sort on integers to
by vitus 7y ago
nit: runtime for radix sort is O(nk), since you sort the full list by each of the digits, sequentially.
I've always thought claiming radix sort on integers to be linear was a bit disingenuous, since k << log(n) only if your list has a lot of duplicate entries.
In fact, if your integers are all unique, then k >= log(n).
(for consistent choice of base for log)
- loeg 7y agoYou're totally right. joshuamorton made the same correction on another comment where I made the same error. Mea culpa!
- repsilat 7y ago> (for consistent choice of base for log) It's not clear the choice of log should be consistent. For radix sort the number of iterations is the log of the max element in the base of the number of buckets. For a merge sort the number of comparisons is pretty close to log-base-two of the number of elements to sort. (Not exactly -- to merge n items you need n-1 comparisons, not n.) Of course, asymptotically they're the same -- lg(n) == log(n) etc -- and we're counting comparisons on one two-fingered hand and divs+mods on the other, so non-asymptotic comparisons don't make much sense without also talking about benchmarks.