Disprove sorting in O(log(n))

Question

Assume an array $X=[x_1,...,x_n]$ is given, where each $x\in X$ is an integer. Array $X$ is sorted if $x_1 \le ... \le x_n$. Typical sorting algorithms have a worst-case performance of $\mathcal{O}(n\log n)$, while in some models of computation, e.g., random-access machines, this can be reduced to $\mathcal{O}(n)$ under specific circumstances.

However, the statement

There exists an algorithm that sorts any $X$ in $\mathcal{O}(\log n)$ time in the worst-case.

seems like nonsense to me. Is there some rigorous refutation of the above statement? I am aware of high-level arguments such as

• "Just reading $X$ takes at least $\mathcal{O}(n)$ time"
• "The sorted array needs $\mathcal{O}(n)$ space, and the runtime of an algorithm is bounded from below by the space it needs"

but these arguments aren't really helpful for a rigorous refutation of the above statement. According to my understanding, such a refutation would need to show that

for every algorithm $A$ in every reasonable model of computation, there exists an $X$ such that $A$ does not correctly sort $X$ in $\mathcal{O}(\log n)$ time.

This is not homework, and I do not have a source for the above statement.

Answer 1

The first argument does help with a rigorous refutation for the statement.

If you want to really be formal, here is how you should approach it (its not a formal proof, but more of a sketch for how you should prove it formally):

Assume towards contradiction there is some algorithm $A$ that solve this question in $o(n)$ time. Since the run-time of $A$ is asymptotically smaller than $n$, then, when taking a big enough $n$, for any $X$ with $n$ elements there must be at least two indices that $A$ doesn't check. Therefore, if we swap the values (or at least, change the values so now any sorted array will have them in opposite order) - since $A$ never checked them, the computation history must be the same, and thus also all swaps it did were the same. However - $A$ never accessed those two indices and hence also never swapped them back to their correct position - which means that either the final array on the original $X$, or on the changed $X$, must be incorrect. Therefore, we get a contradiction to that we assumed $A$ solves this question, and hence $A$ must work in at least $\Omega(n)$ in order to actually sort.

Answer 2

This would depend on context. You can't do a comparison based sort with less than log (n!) comparisons, and that's $\Theta(n \log n)$. But the statement doesn't say "comparisons", it says "time".

With unlimited resources, say with $n^2$ processors that can all run in parallel, it might very well be possible. Finding the maximum of n values in O (log n) is quite easy with n processors. Sorting in O (log n) will be harder and needs more cleverness than I have in 5 minutes, but I wouldn't be surprised if it can be done.