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(n log n) time. There are also O(n) algorithms which are better suited for large n. The special case of drawing n sorted observations from the uniform distribution on [0,1] is equivalent to drawing from the uniform distribution on an n-dimensional simplex; this task is a part of sequential importance resampling.