An Algorithm for Merging Disk Files in Place

Abstract

An algorithm is presented for sorting a random access file in place. The algorithm is unique in the sense that no auxiliary storage, apart from a number of buffers in the machine's high-speed memory, is required. In addition, the algorithm makes active use of the random access capabilities of rotating magnetic media and cannot be converted to operate on sequential files. The run time is known to be of 0( n log n) under certain circumstances. An example also shows that this run time can deteriorate to 0( n* ), which is probably also the worst-case run time.