Practical in-place merging
- 1 March 1988
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 31 (3) , 348-352
- https://doi.org/10.1145/42392.42403
Abstract
We present a novel, yet straightforward linear-time algorithm for merging two sorted lists 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.Keywords
This publication has 4 references indexed in Scilit:
- Stable duplicate-key extraction with optimal time and space boundsActa Informatica, 1989
- Virtual Memory Behavior of Some Sorting AlgorithmsIEEE Transactions on Software Engineering, 1984
- A simple linear-time algorithm for in situ mergingInformation Processing Letters, 1984
- Stable Sorting in Asymptotically Optimal Time and Extra SpaceJournal of the ACM, 1978