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.

Further reading

• Bentley, Jon Louis; Saxe, James B. (1979), "Generating sorted lists of random numbers", Computer Science Department, Paper 2450, retrieved January 4, 2014 
• Gerontidis, I.; Smith, R. L. (1982), "Monte Carlo Generation of Order Statistics from General Distributions", Journal of the Royal Statistical Society. Series C (Applied Statistics), 31 (3): 238–243, JSTOR 2347997 
• Lurie, D.; Hartley, H. O. (1972), "Machine-Generation of Order Statistics for Monte Carlo Computations", The American Statistician, 26 (1): 26–27, doi:10.1080/00031305.1972.10477319 
• Ripley, Brian D. (1987), Stochastic Simulation, Wiley, pp. 96–98, ISBN 0-471-81884-4