merge m things with n (minimum average)

[Philippe Flajolet <Philippe.Flajolet@inria.fr>]

Philippe Chassaing wrote:
> Exercise 22, p. 209 of Sorting and Searching, by Knuth: 

> Study the minimum average number of comparisons needed
> to merge m things with n.

> has rating [M43] in the last errata version,
>  instead of [M50] in the 1973 edition.
>  I would like very much to know
> the references of the solution
>  if the problem is not open anymore.

> Philippe Chassaing

The solution would have corresponded to page 637 if this hadn't been an
open problem. Therefore, you just need to look at the errata list 
    http://www-cs-staff.Stanford.EDU/~knuth/taocp.html
under page 637, in the errat for volume 3.

This gives a reference to J. Algorithms, 5, 1984, pp. 557-578:
Ramanan-Hyafil, New bounds for selection. The authors say: "One of these
algorithms [for selection] is optimal for a wide range of values of n
and k."

Cheers, Ph.

-- 
---------------------------------------------------
Philippe Flajolet
Algorithms Project, INRIA Rocquencourt
F-78153 Le Chesnay (France)
Tel: +33 (1) 39.63.56.26 / 39.63.54.43 [secr.]
Fax: +33 (1) 39.63.53.87
E-mail: Philippe.Flajolet@inria.fr
WWW: http://www-rocq.inria.fr/algo/flajolet/index.html
 +++ANALYSIS of ALGORITHMS pages:
http://www-rocq.inria.fr/algo/AofA/index.html
---------------------------------------------------