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

      0 references
      0 references
      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
      [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

      Identifiers