2 ms·
Any good hashing function would already be uniformly distributed, right? In that case, using this algorithm over traditional ones makes little sense.
by anilakar 7y ago
Any good hashing function would already be uniformly distributed, right? In that case, using this algorithm over traditional ones makes little sense.
- 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.