Open AccessOptimal Time-Space Trade-Offs for Sorting
Author(s) -
Jakob Pagter,
Theis Rauhe
Publication year - 1998
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v5i10.19282
Subject(s) - upper and lower bounds , sorting , logarithm , product (mathematics) , mathematics , space (punctuation) , combinatorics , range (aeronautics) , computation , binary logarithm , omega , log log plot , discrete mathematics , algorithm , computer science , mathematical analysis , physics , geometry , materials science , quantum mechanics , composite material , operating system
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.