An Efficient Algorithm for Computing Optimal Desk Merge Patterns (Extended Abstract)

In this paper, we present an algorithm which computes the optimal pattern for merging n equal size sorted sequences stored on a disk, in time O(log n) and constant space. The best previously known algorithm for solving this problem (Knuth [4], Schlumberger-Vuillemin [5]) takes time O(n 2 ) and space O(n).

Authors

• Laurent Hyafil
• F. Prusker
• Jean Vuillemin

Keywords

• Analysis of algorithms
• Direct access devices
• Merging
• Sorting