81–90 of 110 posts
Earlier quoted context omitted.
I think it's different in that you don't care what the output of a hash is, as long as it's sufficiently unique or whatever. Whereas here the buckets are are intimately tied to the input. It's more of an arithmetic hack I'd say, as it only works on decimal numbers
Radix sort works in any base
Earlier quoted context omitted.
No one is claiming that this sort algorithm (or any other) is asymptotically faster than O(n log(n)). It can be mathematically proved that no sort algorithm can improve on this. The object with sort algorithms is to find one with good constant-factor performance on typical inputs. Frankly, I am more persuaded by the arguments in favor of an algorithm like "Tim-sort", which doesn't claim to micro-optimize hardware mor…
I'm quite a noob, and this is a bit off-topic, but if it's mathematically proven that no sorting algorithm can be faster then O(n*log(n)), but we know for sure that checking if an array is sorted is O(n), then doesn't that prove that P ≠ NP?
C's qsort() is notoriously bad because the comparison function isn't inlined, meaning the majority of time is spent in call overhead. Zhangxp1998 ported quadsort to C++ and compared with std::sort and found it to be slower: https://gist.github.com/zhangxp1998/0e2fa30656c894017d183e0d... Shameless self promotion, if you want a faster sorting implementation, check out pdqsort ( https://github.com/orlp/pdqsort ) which i…
Comparing a stable sort to a normal sort is unfair. Compare it with std::stable_sort.
Earlier quoted context omitted.
Only in the random case. Already sorted in either direction and it's ~10x slower.
Who wants to sort sorted data. If the input data is more often sorted, you can test this before sorting.
Earlier quoted context omitted.
Radix sort works in any base
Radix sort also works on strings, etc. (anything that can be lexicographically ordered)
Earlier quoted context omitted.
"Mostly-sorted" is a very vague definition.
Usually what people mean by mostly sorted in CS is that there is some small K such that each element in the input is no more than K places from the position it would be in if the input was sorted.
qsort has to invoke your comparison function repeatedly, which incurs a lot of overhead. Try C++'s std::sort
This feels a little unfair; the function is invoked the same number of times, but C++ has a mechanism for removing the overhead of calling a function (inlining).
C's qsort() is notoriously bad because the comparison function isn't inlined, meaning the majority of time is spent in call overhead. Zhangxp1998 ported quadsort to C++ and compared with std::sort and found it to be slower: https://gist.github.com/zhangxp1998/0e2fa30656c894017d183e0d... Shameless self promotion, if you want a faster sorting implementation, check out pdqsort ( https://github.com/orlp/pdqsort ) which i…
Comparing a stable sort to a normal sort is unfair. Compare it with std::stable_sort.
Earlier quoted context omitted.
Usually what people mean by mostly sorted in CS is that there is some small K such that each element in the input is no more than K places from the position it would be in if the input was sorted.
According to this definition, the "random tail" test data is not "mostly sorted".