average case: mergesort

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

> Hallo. I'm an italian computer science's student. I need of average
case mergesort analysis's,
> but i not find in bokks or internet.
> Can you help me?    Excuse me for my english.

Various implementations of MergeSort can be found in Vol 3 of The Art of
Computer Programming
by Knuth. See pages 158-168. The analyses known at the time are to be
found in exercises
mentioned in the text. See esp. Exercise 5.2.4-14 (and the solution).

We now know a bit more. For instance, there are systematically
fluctuations present in this
type of divide-and-conquer algorithm. In a way, the "average-case
behaviour is fractal".
Golin and I had a paper a few years back: see e.g.
Mellin Transforms and Asymptotics : The Mergesort Recurrence (104kb), P.
Flajolet, M Golin. In Acta Informatica , vol. 31, 1994, pp. 673-696.
(A preliminary version is to be found at
http://algo.inria.fr/flajolet/Publications/).
There we also get a limiting distribution that is of the Gaussian type.
Hwang (no web page?) has further results on this. These results concern
the "top down recursive" version of mergesort (split
n->ceil(n/2),floor(n/2)).
Helmut Prodinger has analysed other versions but I cannot access his
page right at this moment.

You may also refer to the Research Pages under the AofA site
http://algo.inria.fr/AofA/Research/08-97.html
http://algo.inria.fr/AofA/Research/09-97.html
wherev Mergesort is briefly mentioned.

--
---------------------------------------------------
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.55.96
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
---------------------------------------------------