An Algorithm for Merging Disk Files in Place
P. P. Roets · Unisa Institutional Repository (University of South Africa) · 1979
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.