Practical in-place merging

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.

REFERENCES

• 1: Alanko, T.O., Erkio, H.H., and Haikala, l.J. Virtual memory behavior of some sorting algorithms. IEEE Trans. on Software Engr. 10 (1984), 422-431.
• 2: S. Dvorák , Branislav Durian, Towards an Efficient Merging, Mathematical Foundations of Computer Science 1986, p.290-298, August 25-29, 1996
• 3: Edward C. Horvath, Stable Sorting in Asymptotically Optimal Time and Extra Space, Journal of the ACM (JACM), v.25 n.2, p.177-199, April 1978 [doi>10.1145/322063.322064]
• 4: Huang, B.C., and Langston, M.A. Fast stable merging and sorting in constant extra space, Computer Science Department Technical Report CS-87-170, Washington State University, 1987.
• 5: B.-C. Huang , M. A. Langston, Stable duplicate-key extraction with optimal time and space bounds, Acta Informatica, v.26 n.5, p.473-484, 1989 [doi>10.1007/BF00289147]
• 6: Huang, B.C., and Langston, M.A. Stable set and multiset operations in optimal time and space, Computer Science Department Technical Report CS-87-166, Washington State University, 1987.
• 7: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 8: Kronrod, M.A. An optimal ordering algorithm without a field of operation (in Russian}, Dok. Akad. Nauk SSSR 186 (1969), 1256-1258.
• 9: Heikki Mannila , Esko Ukkonen, A simple linear-time algorithm for in situ merging, Information Processing Letters, v.18 n.4, p.203-208, May 1984 [doi>10.1016/0020-0190(84)90112-1]
• 10: Pardo, L.T. Stable sorting and merging with optimal space and time bounds. SIAM 1. Comput. 6 (1977), 351-372.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: Maintenance**

General Terms:
Algorithms, Theory