Optimal Time-Space Trade-Offs for Sorting

  • Jakob Pagter
  • Theis Rauhe

Abstract

We study the fundamental problem of sorting in a sequential model of computation and in particular consider the time-space trade-off (product of time and space) for this problem.
Beame has shown a lower bound of  Omega(n^2) for this product leaving a gap of a logarithmic factor up to the previously best known upper bound of O(n^2 log n) due to Frederickson. Since then, no progress has been made towards tightening this gap.
The main contribution of this paper is a comparison based sorting algorithm which closes this gap by meeting the lower bound of Beame. The time-space product O(n^2) upper bound holds for the full range of space bounds between log n and n/log n. Hence in this range our algorithm is optimal for comparison based models as well as for the very powerful general models considered by Beame.
Published
1998-01-10
How to Cite
Pagter, J., & Rauhe, T. (1998). Optimal Time-Space Trade-Offs for Sorting. BRICS Report Series, 5(10). https://doi.org/10.7146/brics.v5i10.19282