scientific article; zbMATH DE number 4020488
[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)\).
- Algorithms for parallel memory, I: Two-level memories
- I/O-space trade-offs. (Extended abstract)
- Lower bounds for external algebraic decision trees
- Strong I/O lower bounds for binomial and FFT computation graphs
- Efficient Bundle Sorting
- scientific article; zbMATH DE number 1445385 (Why is no real title available?)
- Algorithmic Building Blocks for Asymmetric Memories
- The buffer tree: A new technique for optimal I/O-algorithms
- A general lower bound on the I/O-complexity of comparison-based algorithms
- Lower bounds for external memory integer sorting via network coding
- Lower bounds for external memory integer sorting via network coding
- Ranked Document Retrieval in External Memory
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)