Average-Case Analysis of the Merging Algorithm of Hwang and Lin

Abstract.

We derive an asymptotic equivalent to the average running time of the merging algorithm of Hwang and Lin applied on two linearly ordered lists of numbers a ₁ <a ₂ <. . . <a _m and b ₁ <b ₂ < . . . <b _n when m and n tend to infinity in such a way that the ratio $\rho$ = m/n is constant. We show that the distribution of the running time is concentrated around its expectation except when $\rho$ is a power of 2. When $\rho$ is a power of 2, we obtain an asymptotic equivalent for the expectation of the running time.