On the Expected Lengths of Sequences Generated
in Sorting by Replacement Selecting

In the replacement-selecting technique of sorting,
one is interested in the ratio L(j) of the 
expected length of the j-th sequence generated by the
technique to the number of memory cells used.  
Using complex-variable theory, it is shown that L(j)
-> 2 and that, asymptotically, the average interval 
between sign changes of L(j)-2 is 2.6662.

CACM July, 1969

Hooker, W. W.

replacement selecting, sorting, sequence lengths,
asymptotic expected length, recursion relation, 
generating function, meromorphic function

3.74 5.31

CA690713 JB February 15, 1978  6:37 PM

1867	4	1867
2272	4	1867
1638	5	1867
1867	5	1867
1867	5	1867
1867	5	1867