# The expected time to sort $n$ elements is bounded below

Prove that the expected time to sort $n$ elements is bounded below by $cn \log n$ for some constant $c$.

Could you give me some hints how I could do that?

• Is this for a specific algorithm? – Robert Israel Dec 8 '14 at 0:47
• @RobertIsrael No, it is not for a specific algorithm. It is for every comparison sort. – Mary Star Dec 8 '14 at 0:50

## 2 Answers

It's false as stated. For instance, radix sort is $O(n)$ (but see @mlo105's answer as well). But if you're talking about comparison-based sorting, it's true.

One proof (sketch): consider all possible inputs to the algorithm and draw an execution tree, where each internal node represents a comparison and its two out-edges are the two branches that could be taken as a result of that comparison, depending on the input data. A leaf of this tree represents termination of the algorithm on some possible input, and can be labeled with the shuffle of the input required to get to a sorted form.

Because there are $n!$ possible outputs (corresponding to the $n!$ ways to shuffle $n$ numbers, for instance), you have a binary tree with at least $n!$ leaves. It must therefore have depth at least $log_2 (n!)$, which is $O(n \log_2 n)$, by, say, Stirling's approximation.

Oh...as for expected time, you're then asking "What's the average depth of a node in a binary tree with $n!$ leaves?"

Well, I can't answer that, but I can show it's larger than the min depth $k = \lceil n \log_2 n \rceil$ of such a tree.

For any leaf $A$ whose depth is greater than $k$, take some leaf $L$ whose depth is LESS than $k$, replace it with a node whose left child is $L$ and whose right child is $A$. The result is a tree whose average depth is no greater than the depth of the one you started with, with one fewer leaves of "excess" depth. Repeat this process until all leaves are at depth no more than $k$. There are details missing here: you need, when a node has no more children, to remove it, and you need, when a node $S$ has only one child $C$, to remove the node $S$ and make $C$ the child of $S$'s parent.

But the idea is clear enough -- just move stuff up, without increasing the average path-length to the root. [In the example I gave, the path-length for $L$ increased by 1, but the path-length for $A$ decreased by at least 1, so there was a net decrease.]

• While this reasoning is sound, it deals with worst, not with the expected (= average) number of comparisons. – Peter Košinár Dec 8 '14 at 0:57
• Now it does. :) – John Hughes Dec 8 '14 at 0:58
• Stirling's approximation is a bigger hammer than you need to show that $\log_2(n!) > cn$. It suffices to observe that $n!$, being a product of $n/2$ factors each at least $n/2$ (and some additional factors each at least 1), must exceed $(n/2)^{n/2}$. – MJD Dec 8 '14 at 1:56
• Good point. I was trying to be terse, but was unnecessarily so. – John Hughes Dec 8 '14 at 3:58

Radix Sort is an interesting one. In practice, it performs in linear time $O(kn)$. In theory, it is possible to argue $k = log(n)$, where $n$ is the number of elements. Suppose we are considering an array of $n$ consecutive elements. Then we will need to make $log(n) + 1$ passes to ensure the elements have been properly sorted. If we consider $1, ..., 100$, we need $log_{10}(100)$ passes. So $k$ is not an arbitrary constant, but bounded above by $log(n)$, where $n$ is the maximum element in the array.

Binary sort is one that does perform in $\Theta(n)$. Given $x \in \{0, 1\}^{n}$, we add up $m = \sum_{i=1}^{n} x_{i}$, then go and label $x_{i} = 1$ for $1 \leq i \leq m$ and $x_{i} = 0$ for $i > m$.

We can write binary sort as a parallel algorithm using threshold functions: $x_{sort}(x) = (\tau_{1}(x), \tau_{2}(x), \tau_{3}(x), ..., \tau_{n}(x))$, where $\tau_{k}(x)$ denotes the threshold-k function (at least $k$ bits in $x$).

To show the result, I agree that Stirling's approximation isn't necessary. We can use the trick that $log(n!) \leq log(n^{n})$ for $n \in \mathbb{N}$. Then by rule of logs, $log(n^{n}) = n log(n)$.

• Nice point about radix-sort, etc. – John Hughes Dec 9 '14 at 0:07