3 ms·
> Any good hashing function would already be uniformly distributed, right? In that case, using this algorithm over traditional ones makes little sense. I think
by adwn 7y ago
> Any good hashing function would already be uniformly distributed, right? In that case, using this algorithm over traditional ones makes little sense.
I think you're misunderstanding Paperweight's post and/or the idea behind flashsort. Hashes are uniformly distributed, hence you can use flashsort (instead of mergesort, quicksort, etc.) and get a time complexity of O(n) instead of O(N*log(N)).
- anilakar 7y agoMany sorting algorithms that work on uniform distributions do exist and they often use plain old insertion sort under the hood. As I see it, Flashsort only exploits that by knowing the CDF beforehand, you can turn the data piecewise linear and then use more classic methods on that.