Simplified stable merging tasks. (English) Zbl 0641.68092

Salowe, Jeffrey; Steiger, William

J. Algorithms 8, 557-571 (1987).

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

MSC:

68P10	Searching and sorting
68Q25	Analysis of algorithms and problem complexity

Keywords:

stable sorting; merging algorithm