Hacker News Reader

An array of sorted hashes is also nice combined with interpolation search [0] (or hinted binary search) which can give a nice speedup compared to "naive" binary search.

[0] https://en.wikipedia.org/wiki/Interpolation_search

Why would you want to sort hashes? Not sure I see the application for hashes here, but that's totally my fault.

To have a duplicable traversal order.

Any good hashing function would already be uniformly distributed, right? In that case, using this algorithm over traditional ones makes little sense.

> 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)).

Many 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.