What can we sort in o(nlog n) time?
Amir M. Ben-Amram, Zvi Galil · 2002
We define two conditions on a random access machine (RAM) with arithmetic and Boolean instructions and possible bounds on word and memory sizes. One condition asserts that we either restrict attention to short words or allow non-uniform programs. The second asserts that we either allow a large memory or a double-precision multiplication. Our main theorem shows that the RAM can sort in o(nlog n) time if and only if both of these conditions hold. This theorem breaks down into four upper bounds only one of which has been known before, and two lower bounds neither of which has been known.>