The I/O Complexity of Sorting and Related Problems (Extended Abstract)

摘要: We provide tight upper and lower bounds, up to a constant factor, for the number of accesses (I/Os) secondary storage required four sorting-related problems: sorting, fast Fourier transform (FFT), permutation networks, permuting records. The bounds hold both in worst case average case. Secondary is modeled as magnetic disk capable transfering P blocks each containing B records single time unit; block must be input from or output contiguous locations on disk. give two optimal algorithms problems, which are variants merge sorting distribution sorting. In particular we show P=1 that standard algorithm an external method. Our use same I/Os does phase key except when internal memory size extremely small, thus substantiating popular adage not better. also simpler more direct derivation result due Hong Kung, gives FFT bound special B=P=O(1).