No label defined (Q3763598)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4020488
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4020488 |
Statements
1987
0 references
upper and lower bounds
0 references
sorting
0 references
fast Fourier transform
0 references
permutation networks
0 references
permuting records
0 references
0.8658737540245056
0 references
0.8118588328361511
0 references
0.807789146900177
0 references
[For the entire collection see Zbl 0616.00013.] We provide tight upper and lower bounds, up to a constant factor, for the number of accesses (I/Os) to secondary storage required for four sorting- related problems: sorting, the fast Fourier transform (FFT), permutation networks, and permuting records. The bounds hold both in the worst case and in the average case. 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. 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 substantiating the popular adage that key sorting is not better. We also give a simpler and more direct derivation of a result due to Hong and Kung, which gives the FFT lower bound for the special case \(B=P=O(1)\).
0 references