AbstractWe present an algorithm for sorting efficiently with parallel, two-level memories. Our main result is an elegant, easy-to-implement, optimal, deterministic algorithm for external sorting with D disk drives. This results answers in the affirmative the open problem posed by Vitter and Shriver of whether an optimal algorithm exists that is deterministic. Our measure of performance is the number of parallel input/output (I/O) operations, in which each of the D disks can simultaneously transfer a block of B contiguous records. We assume that internal memory can hold M records. Our algorithm sorts N records in the optimal bound of Theta((N/BD) log (N/B)/log (M/B)) deterministically, and thus it improves upon Vitter and Shriver's optimal randomized algorithm as well as the well-known deterministic but nonoptimal technique of disk striping. It is also practical to implement. Copyright 1995 by ACM, Inc.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Categories and Subject Descriptors: B.4.4 [Input/Output and Data Communications]: Performance Analysis and Design Aids -- worst-case analysis; F.1.2 [Computation by Abstract Devices]: Modes of Computation -- parallelism and concurrency; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- sorting and searching; E.5 [Files] -- sorting/searching
General Terms: Algorithms
Additional Key Words and Phrases: I/O complexity, parallel disks, parallel I/O, merge sort
Selected papers that cite this one
- Lars Arge, Paolo Ferragina, Roberto Grossi, and Jeffrey Scott Vitter. On sorting strings in external memory (extended abstract). In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 540-548, El Paso, Texas, 4-6 May 1997.
Selected references
- Alok Aggarwal and Jeffrey Scott Vitter. The input\slash output complexity of sorting and related problems. Communications of the ACM, 31(9):1116-1127, September 1988.
- M. Ajtai, J. Komlós, and E. Szemerédi. An O(n log n) sorting network. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pages 1-9, Boston, Massachusetts, 25-27 April 1983.
- Shimon Even. Parallelism in tape-sorting. Communications of the ACM, 17(4):202-204, April 1974.
- D. Gifford and A. Spector. The TWA reservation system. Communications of the ACM, 27(7):649-669, July 1984.
- Jia-Wei Hong and H. T. Kung. I/O complexity: The red-blue pebble game. In Conference Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computation, pages 326-333, Milwaukee, Wisconsin, 11-13 May 1981.
- Tom Leighton. Tight bounds on the complexity of parallel sorting. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pages 71-80, Washington, D.C., 1984.
- Jeffrey Scott Vitter and Elizabeth A. M. Shriver. Optimal disk I/O with parallel block transfer (extended abstract). In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 159-169, Baltimore, Maryland, 14-16 May 1990.