| Asymptotically efficient in-place merging | |
| Authors: | Jyrki Katajainen, Tomi Pasanen, and George Titan |
| Published in: | Proceedings of the 20th Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 969, Springer-Verlag (1995), 211-220 |
| DOI: | 10.1007/3-540-60246-1_127 |
| Copyright: | © Springer-Verlag |
| Abstract: | Two new linear-time algorithms for in-place merging are presented. Both algorithms perform at most (1+t) m + n/2t + o(m) element comparisons, where m and n are the sizes of the input sequences, m≤ n, and t= ⌊ log2(n/m)⌋. The first algorithm is for unstable merging and it carries out no more than 4(m+n) + o(n) element moves. The second algorithm is for stable merging and it accomplishes at most 15m +13n + o(n) moves. |
| Related: |  HTML (Journal article) |
| BibLATEX: | @inproceedings{KPT1995bC,
author = {Jyrki Katajainen and Tomi Pasanen and George Titan},
title = {Asymptotically efficient in-place merging},
booktitle = {Proceedings of the 20th Symposium on Mathematical Foundations of
Computer Science},
series = {Lecture Notes in Computer Science},
volume = {969},
publisher = {Springer-Verlag},
year = {1995},
pages = {211--220},
}
|