An Optimal in-Situ Disk Sorting Algorithm Based on Heapsort

A versatile variant of Heapsort, adapted for external disk sorting, is presented. On a single processor RAM with internal memory capacity Θ(m + kbw) words, it sorts a file of n records of length w words, stored in m physical blocks, each consisting of b records, on a disk, using O(m log m/ log k) input/output operations, and O(n log n) internal key comparisons, for any k ≥ 2. For internal memory of capacity s words, with s = Θ(m) = Θ(kbw), the previous estimate is asymptotically optimal. However, unlike the other known disk sorting algorithms of comparable time efficiency, the new algorithm sorts the file in-situ -- i.e., without using any other additional external working files. Moreover, a simple general algorithm is proposed that on a multiprocessor machine consisting of p RAMs of the previous type, connected in a line, each of them equipped by its own external disk memory, enables to achieve within a certain range a linear speed-up of any external sorting algorith..