
doi: 10.1137/0207002
A simple partitioning algorithm for merging two disjoint linearly ordered sets is given, and an upper bound on the average number of comparisons required is established. The upper bound is $1.06\log _2 \begin{pmatrix} {n + m} \\ m \end{pmatrix}$, where n is the number of elements in the larger of the two sets, m the number of the smaller, and $\begin{pmatrix} {n + m} \\ m \end{pmatrix} = (n + m)!/(m!n!)$. An immediate corollary is that any sorting problem can be done with an average number of comparisons within $6\% $ of the information theoretic bound using repeated merges; it does not matter what the merging order used is. Although the provable bound is $6\% $ over the lower bound, computations indicate that the algorithm will asymptotically make only $3\% $ more comparisons than the lower bound. The algorithm is compared with the Hwang-Lin algorithm, and modifications to improve average efficiency of this well known algorithm are given.
Algorithms in computer science
Algorithms in computer science
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
