# Asymptotic complexity of sorting using k-comparisons

Sorting using 2-elements comparisons has an asymptotic worst-case complexity of $n \log_2(n)$ (reached by mergesort, heapsort, binary insertion, ford-johnson at least), which is optimal.

If we sort using comparisons that sort k elements as building blocks, the information theoretic lower bound is $n \log_{k!}(n)$. We can easily reach $n \log_k(n)$ with k-ary insertion.

Question: Where is the optimal complexity between $n \log_k(n)$ and $n \log_{k!}(n)$ ?

Appropriate refs would be appreciated too.

Edit : because it wasn't clear :

I'm interested about the complexity in $n$, with $k=O(1)$. It has the asymptotic behavior of $\alpha n\log_2(n)$ with $\alpha \in [\frac{1}{\log_2(k)},\frac{1}{\log_2(k!)}]$, and i'd like more precision about $\alpha$.

## 2 Answers

As I was told by Abhishek Methuku, this has been studied already, in fact several times, see e.g. http://www.researchgate.net/publication/3042594_Sorting_n_objects_with_a_k-sorter

For $k$ large, the answer is close to $n \log_{k!}(n)$ but e.g. $k=3$ seems to be open.

First, lets bring those into what I think is the right form to look at.

$\Theta\left(n\cdot \log_k(n)\right) \: = \: \Theta\left(n\cdot \frac{\log_2(n)}{\log_2(k)}\right) \: = \: \Theta\left(\frac{n\cdot \log_2(n)}{\log_2(k)}\right)$

and

$\Theta\left(n\cdot \log_{k!}(n)\right) \: = \: \Theta\left(n\cdot \frac{\log_2(n)}{\log_2(k!)}\right) \: = \: \Theta\left(\frac{n\cdot \log_2(n)}{k\cdot \log_2(k)}\right)$

Observe that a $k$-ary comparison suffices for $\: \left\lfloor \frac{k}2 \right\rfloor \:$ simultaneous (binary) comparisons.

For $\: 2\leq k \:$, $\:$ $\;\; \left\lfloor \frac{k}2 \right\rfloor \: \in \: \Theta(k) \;\;$.

By the AKS network, for $\: 2\leq k\leq O(n) \:$, $\:$ $O\left(\frac{n\cdot \log_2(n)}k\right)$ $k$-ary comparisons are sufficient to sort.

When $\: n\leq k \:$, $\:$ $1 \:\: k$-ary comparison is sufficient to sort. $\quad$ $1\in O\left(\frac{n\cdot \log_2(n)}k\right)$

Therefore, for $\: 2\leq k \:$, $\:$ $O\left(\frac{n\cdot \log_2(n)}k\right)$ $k$-ary comparisons are sufficient to sort.

$5$ $k$-ary comparisons suffice for a $\: \left(4\cdot \left\lfloor \frac{k}2 \right\rfloor \right)$-ary $\:$ comparison.

For $\: 4\leq k \:$, $\:$ $5\:\:k$-ary comparisons suffice for a $\: \left(\frac32 \cdot k\right)$-ary $\:$ comparison.

For $\: 2\leq k\leq n \:$, $\:$ $\log_{\frac32}\left(\frac{n}k\right) = \frac{\log_2\left(\frac{n}k\right)}{\log_2\left(\frac32\right)} \:$.

For $\: 2\leq k\leq n \:$, $\:$ $5^{\left\lceil \frac{\log_2\left(\frac{n}k\right)}{\log_2\left(\frac32\right)} \right\rceil}$ $k$-ary comparisons are sufficient to sort.

For $\: 2\leq n \:$, $\:$ at least one $k$-ary comparison is necessary to sort.

Therefore, for $\: 2\leq k\leq n \:$ and $\: \frac{n}k \in O(1) \:$, $\:$ sorting takes exactly $\Theta(1)$ $k$-ary comparisons.

I suspect one could refine the second of my two
conclusions to show that your lower bound is achieved.

• Not what i had in mind, but still nice. I'm interested about the complexity in $n$, with $k=O(1)$. It has the asymptotic behavior of $\alpha nlog_2(n)$ with $\alpha \in [\frac{1}{log_2(k)},\frac{1}{log_2(k!)}]$, and i'd like more precision about $\alpha$. About your point of view, i don't think you'll reach the lower bound that way, because $5^{\frac{\log_2\left(\frac{n}k\right)}{\log_2(\frac32)} } = O((\frac{n}{k})^{\frac{log_2(5)}{log2(\frac32)}})$ which won't do it. Jun 19, 2012 at 12:12
• I was going to interpret it that way before I realized that, as far as I can find, $\hspace{1.2 in}$ the optimal constant is not known even for $\: k = 2 \:$. $\;\;$
– user6973
Jun 19, 2012 at 18:01
• I now realize that your use of base $2$ in the first logarithm you write might address my point. $\hspace{0.3 in}$ Is the optimal number of binary comparisons divided by $\: n\cdot \log_2(n) \:$ known to converge to $1$?
– user6973
Jun 19, 2012 at 18:10
• Yes, for $k=2$ the optimal number of comparisons divided by $n\log_2(n)$ converges to 1. Many algorithms achieve this, the easiest probably being binary insertion (which needs $\sum_{i=2}^{n} \lceil{\log_2(i)}\rceil \sim n\log_2(n)$ comparisons). Jun 19, 2012 at 22:46