Significant Improvements to the Hwang-Lin Merging Algorithm
Glenn K. Manacher · Journal of the ACM · 1979
The Hwang-Lin mergmg algorithm is the best general-purpose merging algorithm that has been found Many improvements to ~t have been devtsed, but these are etther for special values of m and n, the number of ~tems being merged, or else zmprovements by a term less than hnear m n + m when the ratm n/m ~s fixed A new methodology is developed m which, for fixed ratio n/m, It ts possible to decrease the number of comparisons by a factor proporUonal to m, m fact m/12, provided n/m _> 8 and m >_ 24 It is shown that the coefficient ~s not best possible, and a techmque for lmprowng it shghtly to ~ is sketched