Hacker News Reader

And once you do through your dataset once, how do you store your distribution? By binning it into a histogram? This is precisely what bucket sort does. I guess there is a continuum of sorting algorithms between flashsort and bucket sort, according to the granularity of the binning.

View on HN

If you know the type of distribution but not the parameters,you can sometimes go through the data once and estimate the parameter (maybe exactly) without "storing the distribution" via histograms. Eg if you know the data is drawn from a uniform distribution U(a,b) but you don't know a or b.

Maybe this goes without saying, but for a fixed accuracy the number of samples required to estimate the distribution parameters does not depend on the number of samples available. Maybe if you need to sort more samples you need more accuracy, though.

Reply on news.ycombinator.com