Optimal Time-Space Trade-Offs for Non-Comparison-Based Sorting

Rasmus Pagh
Jakob Pagter

January 2001

Abstract:

We study the fundamental problem of sorting $n$ integers of $w$ bits on a unit-cost RAM with word size $w$, and in particular consider the time-space trade-off (product of time and space in bits) for this problem. For comparison-based algorithms, the time-space complexity is known to be $\Theta(n^2)$. A result of Beame shows that the lower bound also holds for non-comparison-based algorithms, but no algorithm has met this for time below the comparison-based $\Omega(n\lg n)$ lower bound.

We show that if sorting within some time bound $\tilde{T}$ is possible, then time $T=O(\tilde{T}+n\lg^* n)$ can be achieved with high probability using space $S=O(n^2/T+w)$, which is optimal. Given a deterministic priority queue using amortized time $t(n)$ per operation and space $n^{O(1)}$, we provide a deterministic algorithm sorting in time $T=O(n\,(t(n) + \lg^* n))$ with $S=O(n^2/T+w)$. Both results require that $w\leq n^{1-\Omega(1)}$. Using existing priority queues and sorting algorithms, this implies that we can deterministically sort time-space optimally in time $\Theta(T)$ for $T\geq n\,(\lg\lg n)^2$, and with high probability for $T\geq n\lg\lg n$.

Our results imply that recent lower bounds for deciding element distinctness in $o(n\lg n)$ time are nearly tight

Available as PostScript, PDF, DVI.

Last modified: 2003-06-08 by webmaster.