# Disprove sorting in O(log(n))

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.

• Note that the sorting problem is at least hard as decision problem $X$ is sorted or not.
– Jut
Sep 2 at 11:34

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.
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.