4 ms·
No, it's not constant time. Depending on implementation details, you end up putting different elements in different buckets in different cache lines and that cr
by exDM69 8y ago
No, it's not constant time. Depending on implementation details, you end up putting different elements in different buckets in different cache lines and that creates side channels.
Radix sort will perform differently for an input that is 1,1,1,... and 1,2,3,...,n.
I have not read up on how djbsort deals with this issue, but it's the problem it's trying to solve.
- Veedrac 8y agoIt's a sorting network, which means it only uses conditional swaps in a fixed pattern, which can be made constant time.