TY - JOUR
AU - Jakob Pagter
AU - Theis Rauhe
PY - 1998/01/10
Y2 - 2020/12/04
TI - Optimal Time-Space Trade-Offs for Sorting
JF - BRICS Report Series
JA - BRICS
VL - 5
IS - 10
SE - Articles
DO - 10.7146/brics.v5i10.19282
UR - https://tidsskrift.dk/brics/article/view/19282
AB - 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.
ER -