The paper by Alok Aggarwal and Jeffrey Scott Vitter provides tight upper and lower bounds for the number of input/output (I/O) operations required for five sorting-related problems: sorting, fast Fourier transform (FFT), permutation networks, permuting, and matrix transposition. The bounds are given both in the worst case and the average case, with constant factors that often match the lower bounds. The secondary storage is modeled as a magnetic disk capable of transferring \( P \) blocks, each containing \( B \) records, in a single time unit. The authors present optimal algorithms for these problems, which are variants of merge sorting and distribution sorting. They show that the standard merge sorting algorithm is optimal for external sorting when \( P = 1 \). The paper also discusses the relationship between the problems and provides a simpler derivation of Hong and Kung's lower bound for the FFT when \( B = P = O(1) \). The results answer several open questions in the pebbling literature and provide tight bounds for the I/O complexity of these problems.The paper by Alok Aggarwal and Jeffrey Scott Vitter provides tight upper and lower bounds for the number of input/output (I/O) operations required for five sorting-related problems: sorting, fast Fourier transform (FFT), permutation networks, permuting, and matrix transposition. The bounds are given both in the worst case and the average case, with constant factors that often match the lower bounds. The secondary storage is modeled as a magnetic disk capable of transferring \( P \) blocks, each containing \( B \) records, in a single time unit. The authors present optimal algorithms for these problems, which are variants of merge sorting and distribution sorting. They show that the standard merge sorting algorithm is optimal for external sorting when \( P = 1 \). The paper also discusses the relationship between the problems and provides a simpler derivation of Hong and Kung's lower bound for the FFT when \( B = P = O(1) \). The results answer several open questions in the pebbling literature and provide tight bounds for the I/O complexity of these problems.