AVERAGE-CASE ANALYSIS OF THE MERGING ALGORITHM OF HWANG AND LIN

We derive an asymptotic equivalent to the average running time of the merging algorithm of Hwang and Lin applied on two linearly ordered lis ts of numbers a(1) < a(2) < ... < a(m) and b(1) < b(2) < ... < b(n) wh en m and n tend to infinity in such a way that the ratio rho = min is constant. We show that the distribution of the running time is concent rated 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 expectati on of the running time.