Simplified stable merging tasks. (English) Zbl 0641.68092

Two distinct algorithms are presented to stably merge two lists in linear time and constant extra space. The first of these new algorithms explicitly generalizes the simple control structure of M. A. Kronrod’s unstable, in-place merging algorithm. This makes the presentation of the algorithm simpler and more accessible than the previously known algorithm for this task, discovered by L. Trabb Pardo. The second of the two algorithms employs a modification to the control structure of Kronrod, and it is even simpler than the first one.
Reviewer: J.Salowe


68P10 Searching and sorting
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI