Generating Sorted Lists of Random Numbers.

The empirical testing of a program often calls for generating a set of random numbers and then immediately sorting them. In this paper we consider the problem of accomplishing that process in a single step generating a sorted list of random numbers specifically, reals chosen uniformly from 0,1. The method we describe generates the randoms in linear time, is perfectly random if it can call a perfectly random generator for a single uniform, and can be described in just three lines of Algol or Pascal code. If the numbers are not required to be generated all at once but are rather to be used one-at-a-time, then the method can be implemented as a subroutine to produce the next number and requires only constant storage. Author