Optimal time-space trade-offs for sorting

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. P. Beame (1991) has shown a lower bound of Ω(n²) for this product leaving a gap of a logarithmic factor up to the previously best known upper bound of O(n² log n) due to G.N. Frederickson (1987). 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 the gap by meeting the lower bound of Beame. The time-space product O(n²) 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