Optimal time-space trade-offs for non-comparison-based sorting
Rasmus Pagh, Jakob Illeborg Pagter · 2002
We study the 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 Θ(n2). 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 Ω(nlgn) lower bound.We show that if sorting within some time bound &Ttilde; is possible, then time T = O(&Ttilde; + nlg* n) can be achieved with high probability using space S = O(n2/T + w), which is optimal. Given a deterministic priority queue using amortized time t(n) per operation and space nO(1), we provide a deterministic algorithm sorting in time T = O(n(t(n) + lg* n)) with S = O(n2/T + w). Both results require that w ≤ n1-Ω(1). Using existing priority queues and sorting algorithms, this implies that we can deterministically sort time-space optimally in time Θ(T) for T ≥ n(lg lg n)2, and with high probability for T ≥ nlg lg n.Our results imply that recent space lower bounds for deciding element distinctness in o(nlgn) time are nearly tight.