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


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


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

  • $\begingroup$ 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. $\endgroup$
    – slan_21
    Jun 19 '12 at 12:12
  • $\begingroup$ 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 \:$. $\;\;$ $\endgroup$
    – user6973
    Jun 19 '12 at 18:01
  • $\begingroup$ 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$? $\endgroup$
    – user6973
    Jun 19 '12 at 18:10
  • $\begingroup$ 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). $\endgroup$
    – slan_21
    Jun 19 '12 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.