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.gif>PS (303 kB)  
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, mn, 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.gif>HTML (Conference paper)  
  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},
This page was generated by Jyrki Katajainen <> on 31.12.2011.