When Can We Sort ino(n log n) Time?

摘要

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 nonuniform 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 ino(n log 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.