Alok Aggarwal
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).
- 1 Beigel, R., and Gill, J. Personal Communication. 1986.Google Scholar
- 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.Google ScholarDigital Library
- 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.Google Scholar
- 4 Hong, J.W., and Kung, H.T. I/O complexity: The red-blue pebble game. In Proceedings of the 13th Annual ACM Symposium on Theory of Computing (Milwaukee, Wisconsin, Oct.}. pp. 326-333. 1981. Google ScholarDigital Library
- 5 Knuth, D.E. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley, Reading, Mass., 1973. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 7 Leighton, F.T. Tight bounds on the complexity of parallel sorting. IEEE Trans. Comput. C-34, 4 (Apr. 1985). Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
Index Terms
- The input/output complexity of sorting and related problems
Recommendations
Some complexity problems on single input double output controllers
We investigate the time complexity of constructing single input double output state feedback controller structures, given the directed structure graph G of a system. Such a controller structure defines a restricted type of P"3-partition of the graph G. ...
Comments