A method is proposed for internal sorting which has the property that the expected time required per record, to sort n records with random keys, is a bounded function of n . Moreover the storage required in addition to that for the records is only 2 n address fields. It appears that the method may be a good choice when the number of records to be sorted is of the order of 10,000 or more. The method consists of partially sorting the records by a radix sort and completing the sort by sifting. In the radix sort, a list type of structure is used to present the distribution of the records.

This paper discusses the testing of methods for generating uniform mlml)crs in a computer--the commonly used multiplicative and mixed congruential generators as well ks two new methods.Tests proposed here are more stringent than those usually applied, because ~he usual tests for randomness have passed severa:l of the commonly used procedures which subsequently gave poor results in actual Monte Carlo calculations.The princi-pal difl!eulty seems to be that certain simple functions of n-tuples of uniform random mlmbers do not have the distribution that probability theory predicts.TwO alternative generating methods are described, one of them using a table of uniform numbers, the other one combining two congruential generators.Both of these methods passed the tests, whereas the conventional multiplieative and mixed congruential methods did not.