What is the state-of-the art on algorithms that calculate/estimate approximate quantiles?
I don't even worry about errors in terms of the value of quantiles (here meaning the cutoff) but having roughly equal sized bins. E.g. if I need vingtiles, I want to have low risk of having any bin having less than 4% of the data or more than 6%.
If I need to implement this in an existing high-level statistical system, I think the question inevitable becomes restricted to downsampling from a population of $N$ to a subsample of $n$ and take quantiles using sorting at costs at the order $O(n \log n)$ instead of $O(N \log N)$, but at the right ratio as a function of the original sample size. I am looking for guidance on how to pick $n$ for any $N$.