ALCOMFT-TR-01-141

Rasmus Pagh and Jakob Pagter
Optimal Time-Space Trade-Offs for Non-Comparison-Based Sorting
Århus. Work package 4. June 2001.

Abstract: 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 Theta(n²). 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(nlg n) lower bound.

We show that if sorting within some time bound T' is possible, then time T=O(T'+nlg^* n) can be achieved with high probability using space S=O(n²/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²/T+w). Both results require that w<= 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>= n (lglg n)², and with high probability for T>= nlglg n.

Our results imply that recent space lower bounds for deciding element distinctness in o(nlg n) time are nearly tight.

Postscript file: ALCOMFT-TR-01-141.ps.gz (263 kb).