Optimal Time-Space Trade-Offs for Non-Comparison-Based Sorting
Rasmus Pagh
January 2001 |

## Abstract:
We study the fundamental problem of sorting integers of
bits on a unit-cost RAM with word size , 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
. 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
lower bound.
We show that if sorting within some time bound is possible, then time can be achieved with high probability using space , which is optimal. Given a deterministic priority queue using amortized time per operation and space , we provide a deterministic algorithm sorting in time with . Both results require that . Using existing priority queues and sorting algorithms, this implies that we can deterministically sort time-space optimally in time for , and with high probability for . Our results imply that recent lower bounds for deciding element distinctness in time are nearly tight
Available as |

Last modified: 2003-06-08 by webmaster.