Sorting by Replacement Selecting In sorting by replacement selecting, the expected length of a sequence beginning with the i-th element (i>1) is proved to be 2F, in accordance with a conjecture of E. H. Friend, where F is the number of memory cells used. The expected length of the j-th sequence is determined to be F times a j-th degree polynomial in e, such that the value of this polynomial approaches 2 as j approaches infinity. Recursive formulas are obtained for both the mean and the standard deviation of the length of the j-th sequence. The mathematical proofs of these results are based upon the assumption that n, the number of items to be sorted, is infinite, but it is shown that the error due to the finiteness of n approaches zero rapidly as n increases. CACM February, 1967 Gasner, B. J. CA670204 JB February 28, 1978 3:56 PM 1638 4 1638 2176 4 1638 2272 4 1638 1638 5 1638 1638 5 1638 1638 5 1638 1867 5 1638 2272 5 1638 677 5 1638 1638 6 1638 1638 6 1638 677 6 1638