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.