Optimal Time-Space Trade-Offs for Non-Comparison-Based Sorting
Rasmus Pagh
January 2001 |
Abstract:
We study the fundamental problem of sorting
![]() ![]() ![]() ![]() ![]()
We show that if
sorting within some time bound
Our
results imply that recent lower bounds for deciding element distinctness in
Available as PostScript, PDF, DVI. |