scientific article; zbMATH DE number 4020488

From MaRDI portal
Publication:3763598





[For the entire collection see Zbl 0616.00013.] We provide tight upper and lower bounds, up to a constant factor, for the number of accesses (I/Os) to secondary storage required for four sorting- related problems: sorting, the fast Fourier transform (FFT), permutation networks, and permuting records. The bounds hold both in the worst case and in the average case. 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. 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 substantiating the popular adage that key sorting is not better. We also give a simpler and more direct derivation of a result due to Hong and Kung, which gives the FFT lower bound for the special case \(B=P=O(1)\).











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3763598)