publication . Article . Other literature type . Report . 1988

The input/output complexity of sorting and related problems

Aggarwal , A.; Vitter , J.S.;
Open Access
  • Published: 01 Aug 1988 Journal: Communications of the ACM, volume 31, pages 1,116-1,127 (issn: 0001-0782, eissn: 1557-7317, Copyright policy)
  • Publisher: Association for Computing Machinery (ACM)
  • Country: France
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 algori...
Subjects
ACM Computing Classification System: Data_FILES
free text keywords: General Computer Science, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], [ INFO.INFO-OH ] Computer Science [cs]/Other [cs.OH]
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue