A machine can compare at most three integers in one run. Show that at least $k(n) := \lceil log_6(n!) \rceil$ runs are needed to sort $n$ integers.

My idea is to use a proof by induction on $$n$$.

For $$n = 1,2,3$$, $$1$$ run is needed so we are done.

Assume the statement is true for sets of $$n$$ or less integers, $$n > 3$$. Let $$S$$ be a set of $$n+1$$ integers, and $$p \in S$$. By the induction hypothesis, it takes at least $$k(n) = \lceil \operatorname{log}_6(n!) \rceil$$ runs of the machine to sort $$S \setminus \{p\}$$.

At this point we’d have a sorted list $$S \setminus \{p\}$$ and want to know where $$p$$ should be inserted into this list. Let $$k’$$ be the number of runs required to do this task. A ternary search on the sorted list $$S \setminus \{p\}$$ could result in $$k’ = \operatorname{log}_3(n)$$ runs in the worst-case scenario (say, if $$p$$ is in the middle of the sorted list $$S \setminus \{p\}$$). Now we’d have:

\begin{align} k(n+1) &= k’ + k(n) \\ &= \operatorname{log}_3(n) + \lceil \operatorname{log}_6(n!) \rceil \\ &\geq \operatorname{log}_6(n+1) + \lceil \operatorname{log}_6(n!) \rceil \\ &\geq \operatorname{log}_6(n+1) + \operatorname{log}_6(n!) \\ &= \operatorname{log}_6((n+1)!), \end{align}

where the first inequality is true since $$\operatorname{log}_3(n) \geq \operatorname{log}_6(n+1)$$ holds for $$n \geq 2$$. So $$k(n+1) \geq \lceil \operatorname{log}_6((n+1)!) \rceil$$.

What I’m not sure of is whether I’m assuming too much what the algorithm would do in obtaining $$k’$$, or if it’s clear ternary search is the fastest way to do this task. Please give some comment.

There are $$n!$$ different possible ways to order the $$n$$ elements. After the first comparison, and subsequent ordering of the three compared elements, there are at still at least $$\frac{n!}{6}$$ possible orders the elements could have. After the second comparison, and subsequent rearrangement, there are at least $$\frac{n!}{6^2}$$ possible orders left.

At the very least, we need to keep going until that number reaches $$1$$. This will take $$\lceil\log_6(n!)\rceil$$ comparisons.

This is an exercise in decision trees. Each run has $$3!=6$$ possible results, but we need to distinguish between $$n!$$ results (corresponding to all permutations of $$n$$ distinct integers). The least depth of the decision tree that will allow for accommodating $$n$$ leaves is $$\lceil\log_6n!\rceil$$.