9
$\begingroup$

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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\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, 2012 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, 2012 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, 2012 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, 2012 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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