Sampling in order
In statistics, some Monte Carlo methods require independent observations in a sample to be drawn from a one-dimensional distribution in sorted order. In other words, all n order statistics are needed from the n observations in a sample. The naive method performs a sort and takes O time. There are also O algorithms which are better suited for large n. The special case of drawing n sorted observations from the uniform distribution on is equivalent to drawing from the uniform distribution on an n-dimensional simplex; this task is a part of sequential importance resampling.
