<p>As I was told by Abhishek Methuku, this has been studied already, in fact several times, see e.g. <a href="http://www.researchgate.net/publication/3042594_Sorting_n_objects_with_a_k-sorter" rel="nofollow">http://www.researchgate.net/publication/3042594_Sorting_n_objects_with_a_k-sorter</a></p>

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

CC BY-SA 3.0
2013-06-09T19:16:54.573Z
2013-06-09T19:16:54.573Z
domotorp
<p>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.</p>

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

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

<p>Appropriate refs would be appreciated too.</p>

<p>Edit : because it wasn't clear :</p>

<p>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$.</p>

<cc.complexity-theory><ds.algorithms><reference-request><sorting>
Asymptotic complexity of sorting using k-comparisons
slan_21
# Asymptotic complexity of sorting using k-comparisons

(Asked by: username_0 on 2012-06-19)

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

**Tags:** cc.complexity-theory, ds.algorithms, reference-request, sorting

---

## 1 answers

### Answer by username_1 on 2013-06-09. Score: 4

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.


---

