Generate sorted vectors of uniformly distributed variates

Efficiently generate sorted p-vectors of variates drawn uniformly from [0,1]

Description

Efficiently generate n sorted p-vectors of variates uniformly from [0,1], i.e. subject to each vector satisfying

     x_1 <= x_2 <= x_3 <= ... <= x_p

Imlements the algorithm from:

(1) Generating Sorted Lists of Random Numbers
Jon Louis Bentley and James B. Saxe
ACM Transactions on Mathematical Software (TOMS)
Volume 6, Issue 3, September 1980

• Acknowledgements: This submission has inspired the following:; Generate random permutation order without using sort()
• MATLAB release: MATLAB 7 (R14)

[Wolfgang Schwanghart]

What makes the function different to the command
x = sort(rand(n,p),2);
? I don't have the cited paper at hand, so it might be good to explain the difference, if there are any.

Best regards,
Wolfgang

[Jos (10584)]

I acknowledge that this is indeed a clever algorithm but in matlab
sort(rand(..)), as already suggested by Wolgang Schwanghart, is much to be prefered. Therefore this submission has only some educational value, for which the internal comments should be expanded.

[Statovic]

The important difference between sort(rand(...)) and this algorithm is that the sort(.) procedure is at best O(n log(n)) time complexity, while this algorithm is linear time, i.e. O(n). For short length vectors the sort(.) approach will be quicker (due to a more efficient implementation of the sort(.) function), but for large n the differences can be significant. As an example:

>> tic;sort(rand(1,10^7),2);toc
Elapsed time is 1.757046 seconds.

vs.

>> tic;genrandsorted(1,10^7);toc
Elapsed time is 0.531082 seconds.

I am guessing that if one implemented the Bentley & Saxe algorithm in C it would probably be comparable to sort(.) for smaller 'n' (and of course, faster again for large 'n').