The input/output complexity of sorting and related problems

TLDR

We provide tight upper and lower bounds, up to a constant factor, on the number of I/Os between internal memory and secondary storage needed for sorting, FFT, permutation networks, permuting, and matrix transposition. We model secondary storage as a magnetic disk that transfers P blocks of B records per time unit, and present two optimal algorithms—variants of merge and distribution sorting—along with a direct derivation of Hong and Kung’s lower bound for the FFT when B = P = O(1). The bounds are tight in both worst‑case and average‑case scenarios, with matching constants in many cases; for P = 1 the standard merge sort is optimal, and our sorting algorithms match the I/O cost of the permutation phase of key sorting except when memory is extremely small, confirming that key sorting offers no speed advantage.

Abstract

We provide tight upper and lower bounds, up to a constant factor, for the number of inputs and outputs (I/OS) between internal memory and secondary storage required for five sorting-related problems: sorting, the fast Fourier transform (FFT), permutation networks, permuting, and matrix transposition. The bounds hold both in the worst case and in the average case, and in several situations the constant factors match. Secondary storage is modeled as a magnetic disk capable of transferring P blocks each containing B records in a single time unit; the records in each block must be input from or output to B contiguous locations on the disk. We give two optimal algorithms for the problems, which are variants of merge sorting and distribution sorting. In particular we show for P = 1 that the standard merge sorting algorithm is an optimal external sorting method, up to a constant factor in the number of I/Os. Our sorting algorithms use the same number of I/Os as does the permutation phase of key sorting, except when the internal memory size is extremely small, thus affirming the popular adage that key sorting is not faster. We also give a simpler and more direct derivation of Hong and Kung's lower bound for the FFT for the special case B = P = O(1).