Fast Stable Merging and Sorting in Constant Extra Space

In an earlier research paper 9 , we presented a novel, yet straightforward linear-time algorithm for merging two sorted list in a fixed amount of additional space. Constant of proportionality estimates and empirical testing reveal that this procedure is reasonably competitive with merge routines free to squander unbounded additional memory, making it particularly attractive whenever space is a critical resource. In this paper, we divise a relatively simple strategy by which this efficient merge can be made stable, and extend our results in a nontrivial way to the problem of stable sorting by merging