| Asymptotically efficient in-place merging | |
| Authors: | Viliam Geffert, Jyrki Katajainen, and Tomi Pasanen |
| Published in: | Theoretical Computer Science 237,1-2 (2000), 159-181 |
| Full text: |  PS (303 kB) |
| DOI: | 10.1016/S0304-3975(98)00162-5 |
| Copyright: | © Elsevier Science B.V. |
| Abstract: | Two linear-time algorithms for in-place merging are presented. Both algorithms perform at most m(t+1) + n/2t + o(m) 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 3(n+m) + o(m) element moves. The second algorithm is for stable merging and it accomplishes at most 5n + 12m + o(m) moves. |
| Related: |  HTML (Conference paper) |
| BibLATEX: | @article{GKP2000J,
author = {Viliam Geffert and Jyrki Katajainen and Tomi Pasanen},
title = {Asymptotically efficient in-place merging},
journaltitle = {Theoretical Computer Science},
volume = {237},
number = {1--2},
year = {2000},
pages = {159--181},
}
|