3 ms·
At some level, even comparing ‘a<b’ has a complexity related to the log of the magnitude of a and b. So if you’re doing a comparison sort over n unique values s
by jameshart 5y ago
At some level, even comparing ‘a<b’ has a complexity related to the log of the magnitude of a and b. So if you’re doing a comparison sort over n unique values surely you’re going to run into a similar log n factor that the gp threw at the radix sort?
- cb321 5y agoIt depends how you count. There can be O(n log(n)^2) as you say, but I believe there are some comparison based algos where you only have to compare "fewer bits" to decide each comparison. So bit-wise cmps might still be O(n log n). However, you do have to move whole w-bit keys which is w bits wide. So, in full cost (cmp + space moves) unless you can do tricks to avoid the whole move, the comparison sorts do scale worse than radix-like digital sorts. And on general purpose CPUs people certainly compare batches of 8/16/32/64 bits at a time in HW. Personally, I think radix really does scale better, but maybe @Kranar can clarify his claim. (EDIT: there is often a random write pattern to digital sorts that can slow them down at massive scales, but that is definitely an {important} constant factor/different kind of "real machine" analysis.)