The input/output complexity of sorting and related problems

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).

REFERENCES

• 1: Beigel, R., and Gill, J. Personal Communication. 1986.
• 2: Blum, M., Floyd, R.W., Pratt, V., Rivest, R.L., and Tarjan, R.E. Time bounds for selection. }. Comput. Syst. Sci. 7 (1973), 448-461.
• 3: Floyd, R.W. Permuting information in idealized two-l, evel storage. In Complexity of Computer Calculations, R. Miller and J. Thatcher, Eds. Plenum, New York, 1972, pp. 105-109.
• 4: Hong Jia-Wei , H. T. Kung, I/O complexity: The red-blue pebble game, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.326-333, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802486]
• 5: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 6: Kwan, S.C., and Baer, J.L. The I/O performance of multiway mergesort and tag sort. IEEE Trans. Comput. C-34, 4 (Apr. 1985), 383-387.
• 7: Tom Leighton, Tight bounds on the complexity of parallel sorting, IEEE Transactions on Computers, v.34 n.4, p.344-354, April 1985 [doi>10.1109/TC.1985.5009385]
• 8: Lindstrom, E.E., and Vitter, J.S. The design and analysis of Bucket- Sort for bubble memory secondary storage. IEEE Trans. Comput. C-34, 3 (Mar. 1985), 218-233.
• 9: Savage, J.E., and Vitter, }.S. Parallelism in space-time tradeoffs, in Advances in Computing Research, Volume 4: Special Issue on Parallel and Distributed Computing. JAI Press, Greenwich, Conn., 1987, pp. 117-146.
• 10: Wu, C.L., and Feng, T.Y. The universality of the shuffle-exchange network. IEEE Trans. Comput. C-30, 5 (May 1981), 324-332.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

  E. Data

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Performance, Theory