Combinatorial aspects of C.A.R. Hoare's FIND algorithm
D.H. Anderson l Operations Research Section, Civil Aviation Authority, Australia, GPO Box 367, Canberra, ACT, 2601 and R. Brown CRA Y Research (Australia) Pty. Ltd. 283 Normanby Rd. Port Melbourne, Vic, 3207 In his invited address to the 1971 IFIP Congress, Donald E: Knuth [1] examined the average performance of C.A.R. Hoare's FIND algorithm [2] for finding the j-th largest out of n elements. Knuth commented that the recurrence relation that he derived was "not the kind of recurrence that we would normally expect to solve". Nevertheless, he went on to solve it, commenting on the "extra.ordinary coincidence" of a certain co:~nmon factor in each of the terms of a derived recurence relation. An extension due to R.C. Singleton [3} to the basic algorithm, knov.;n as "median-of-three selection", has seen widespread use in many important computational techniques applied to a. diverse set of problems. Because of the renewed interest in median-of-three selection, this paper addresses itself to a serious study of its average performance. In this paper the median-of-three selection problem is formulated in combinatorial terms and solved by generating function techniques. Closed form expressions are presented for the average of the underlying distribution. research was undertaken while this author was employed in the Computer Science Department, University College, University of New South 'Vales, Australian Defence Force Academy, Canberra, ACT, 2600. Australasian Journal of Combinatorics ~(1992), pp.l09-119