<p>I think your question was addressed in Beigel and Gill's paper
"<a href="http://doi.ieeecomputersociety.org/10.1109/12.53587">Sorting n objects using k-sorter</a>" from 1990 and the abstract of the paper says it all:</p>

<blockquote>
  <p>A k-sorter is a device that sorts k objects in unit time. The complexity of an algorithm that uses a k-sorter is defined as the number of applications of the k-sorter. In this measure, the complexity of sorting n objects is between $\frac{n \log n}{k \log k}$ and $\frac{4n \log n}{k \log k}$, up to first-order terms in n and k.</p>
</blockquote>

CC BY-SA 3.0
2013-03-17T17:31:03.477Z
Thank you. I couldn't find the paper. Can you provide the link to the paper or its proof?
AmeerJ
CC BY-SA 3.0
2013-03-17T17:50:16.290Z
[link to paper](http://scholar.google.com/scholar?cluster=5722195084700676122&hl=en&as_sdt=0,5)
Neal Young
CC BY-SA 3.0
2013-03-17T20:43:01.593Z
Also on [citeseerx](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.7281).
Kaveh
CC BY-SA 3.0
2013-03-18T16:49:40.293Z
Note that when $k=\sqrt{n}$, Beigel and Gill's bound is $\Theta(\sqrt{n})$.
Jeffε
CC BY-SA 3.0
2013-03-17T17:24:47.797Z
2013-03-17T21:47:46.783Z
2013-03-17T21:47:46.783Z
user14004
<p>It is possible to sort <strong>obliviously</strong> with $O(\sqrt{n}\log n)$ calls to the black box, each applied to a contiguous subarray of the original input.  The algorithm never touches the input data except through black-box calls. In particular, the same sequence of black-box calls is only a function of $n$, not the actual input data (hence "oblivious").</p>

<p>Here is a sketch of a simpler algorithm, which uses a black box that sorts subarrays of size $k$ instead of just $\sqrt{n}$.  The total number of calls to the black box is roughly $2(n/k)^2$.  For notational simplicity, assume that $k$ is even and $2n/k$ is an odd integer.</p>

<pre><code>BlockBubbleSort(X[0..n-1], k):
   m = floor(n/k)
   for i = 1 to m
      for j = 0 to m-1
          BlackBoxSort(X[j*k .. (j+1)*k-1])
      for j = 0 to m-1
          BlackBoxSort(X[j*k + k/2 .. (j+1)*k + k/2 - 1])
</code></pre>

<p>Here is a diagram of the algorithm for $n=18$ and $k=4$.  Data travels from left to right; each box is a $k$-sorter.</p>

<p><img src="https://i.sstatic.net/XpbBI.png" alt="enter image description here"></p>

<p>As the figure hopefully suggests, this algorithm breaks the input array into chunks of size $k/2$, and then applies bubblesort to the chunks, using the $k$-sorter in place of a compare-exchange operation.  Correctness follows by observing that the network <a href="http://en.wikipedia.org/wiki/Sorting_network#Zero-one_principle" rel="noreferrer">correctly sorts any array of 0s and 1s</a>.</p>

<p>As @VinayakPathak's comment suggests, the $O((n/k)^2)$ bound can be reduced by replacing bubblesort with a different sorting network.  For example, <a href="http://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort" rel="noreferrer">Batcher's even-odd mergesort</a> reduces the number of black-box calls to $O((n/k)\log^2(n/k)) = O(\sqrt{n}\log^2 n)$, and the <a href="http://link.springer.com/article/10.1007%2FBF01840378" rel="noreferrer">AKS sorting network</a> reduces it to $O((n/k)\log (n/k)) = O(\sqrt{n}\log n)$.  This last algorithm matches Neal's non-oblivious algorithm up to (large!!) constant factors.</p>

CC BY-SA 3.0
2013-03-20T17:43:35.250Z
thanks. Can a $\Omega(\sqrt n\ lg(n))$ lower bound be proved?
AmeerJ
CC BY-SA 3.0
2013-03-20T18:47:14.410Z
No, Biegel and Gill's paper implies an upper bound of $O(\sqrt{n})$.
Jeffε
CC BY-SA 3.0
2013-03-20T21:22:01.150Z
+1 for that nice picture! I may be mistaken but it seems to me that it is not entirely correct (correct me if I'm wrong). Assuming the output is in ascending order, if the smallest element is in the last position there is no "path" for it to "travel" to the first position. Changing "for i = 1 to m" to "for i = 1 to m+1" seems to correct this, although it might introduce some unnecessary overhead.
George
CC BY-SA 3.0
2013-03-21T05:00:40.603Z
@George Oops, you're right; I need one more layer!
Jeffε
CC BY-SA 3.0
2013-03-18T16:41:34.407Z
2013-03-18T16:51:08.157Z
2013-03-18T16:51:08.157Z
Jeffε
<p>It's possible to sort with $O(\sqrt n\log n)$ calls to the black box and no comparisons.</p>

<p>First, consider the following balanced partitioning problem: given $m$ elements $A[1..m]$ (where $\sqrt n \le m \le n$), partition them into two groups, the smallest of size at least about $m/4$, so that all elements in the first group are smaller than all elements in the second group.  This can be done with $O(m/\sqrt n)$ calls to the black box.  (I'll describe that later.)  Then use quicksort with this partitioning algorithm:</p>

<pre><code>def qsort(A[1..m]):
   if m &lt; sqrt(n): sort A with one call to the black box
   else:
     Partition A[1..m] into two groups as described above.
     Recursively qsort the first group.
     Recursively qsort the second group.
</code></pre>

<p>Assuming each partition step takes $O(m/\sqrt n)$ calls to the black box, the above algorithm, given input $A[1..n]$, will make $O(\sqrt n\log n)$ calls to the black box, because the recursion tree has depth $O(\log n)$ and each level of the tree has a total of $O(n/\sqrt n) = O(\sqrt n)$ calls to the black box.</p>

<p>Do the partitioning step as follows:</p>

<pre><code>def partition(A[1..m]):  (where sqrt(n) &lt;= m &lt;= n)
   Divide A into m/sqrt(n) groups of size sqrt(n) each.
   Sort each group with one call to the black box per group.
   Sort the medians of the groups with one call to the black box.
   (Note the number of groups is less than sqrt(n), because m &lt;= n.)
   Let X be the median of the medians.
   Partition all m elements around X, using the black box as follows:
      For each group G, let Y be its median:
        Call the black box once on (G - {Y}) union {X}.
        (This gives enough information to order all elts w.r.t. X.)
</code></pre>

CC BY-SA 3.0
2013-03-17T17:59:14.957Z
In the last step of the algorithm partition(): "Partition all m elements around X", won't this use m additional comparisions?
Vinayak Pathak
CC BY-SA 3.0
2013-03-17T18:00:30.597Z
See the line just following the algorithm, it explains how to do that step.  I'll edit it to make that clearer.
Neal Young
CC BY-SA 3.0
2013-03-17T17:49:01.207Z
2013-03-18T03:08:30.763Z
2013-03-18T03:08:30.763Z
Neal Young
<p>Assume that we want to sort a list $S$ of $n$ real numbers. 
Assume that we are given a black box that can sort $\sqrt n$ real numbers instantly. 
How much advantage can we gain using this black box? </p>

<p>For example, can we sort the numbers with only $O(\sqrt n)$ calls to the black box? 
The best algorithm that I have found uses $n$ calls to the black box. 
But I haven't been able to improve it further. 
Here is my algorithm which is similar to merge-sort:</p>

<p>First partition the list $S$ into $\sqrt n$ lists $s_1, s_2, ..., s_{\sqrt n}$ with approximately $\sqrt n$ size. 
Then use $\sqrt n$ calls to the black box to sort these lists. 
Finally, merge the sorted lists using the black box as follows: </p>

<p>Put the smallest elements of the lists in a new list $L$, 
then call the black box to sort it. 
The number in $L[1]$ (first and smallest element of $L$) will be 
the smallest number in $S$. 
We can put it in the first place of the output list.<br>
Assuming the element has been chosen from $s_j$, 
we replace $L[1]$ with the second smallest element of sort list $s_j$, 
and again run the black box on it to compute the second smallest member of $S$.<br>
We continue till all the elements are sorted. The total number of black box calls for this part will be $n - \sqrt n$. Therefore overall the total number of calls will be $n$.</p>

<p>On the other hand, it looks like we should be able to obtain a lower-bound using the lower-bound on the number comparisons needed for sorting as follows:
We can implement the black box using $\sqrt n \lg \sqrt n = \frac{1}{2} \sqrt n \lg n$ comparisons. 
If we can solve the problem with $o(\sqrt n)$ calls to the black box and merging in linear-time we can sort $n$ real numbers with $o(n \lg n)$ comparisons which is impossible.</p>

<p>I guess we could prove that $\Omega(n)$ is a lower-bound for the number of calls to the black box, since lots of comparisons using in the black box would be shared and therefore are recounted in our argument. </p>

<p><strong>UPDATE:</strong> As the the other posts suggest, an $\sqrt n \lg n$ is also achievable.</p>

CC BY-SA 3.0
2013-03-17T15:26:20.307Z
Isn't it obvious that this cannot be done in less than linear number of operations in the size of the input i.e. $N$? What do you mean by comparisons? You should probably be more specific about the model of computation you are using, e.g. [real RAM](http://en.wikipedia.org/wiki/Real_RAM) model.
Kaveh
CC BY-SA 3.0
2013-03-17T15:33:07.570Z
Oh ... you're right. I meant the number of usages of the machine. You should only use the machine for comparisons. I'm updating the question.
AmeerJ
CC BY-SA 3.0
2013-03-17T15:50:26.783Z
To make my statement about comparisons more clear, I'd prove that if you use the machine less than $O(\sqrt N)$ times, I could sort $N$ numbers faster than $O(N log N)$. Because if I replace your imaginary machines with a real algorithm, say merge sort, each one requires a $\sqrt N log{\sqrt N } = 1/2 {\sqrt N} log N$ and thus the sorting is done in less than $\sqrt N * O(\sqrt N * log N) \approx O(N log N)$ which is not possible.
AmeerJ
CC BY-SA 3.0
2013-03-17T15:54:09.580Z
There seems to be a typo in your comment. Did you mean to say: "no algorithm using less than $\sqrt{N}$ calls to the machine can sort $N$ real numbers with less than $N\lg N$ comparisons"? ps: you should also be careful about the fact that the $N\lg N$ lower-bound only holds for comparison based sorting algorithms.
Kaveh
CC BY-SA 3.0
2013-03-17T16:35:17.500Z
I edited the question for readability. Fill free to roll back or edit further. I am not sure what you mean by the last line though. ps: In a way, you are asking about a good self-reduction from sorting to itself. Note that we can also use a self-reduction recursively, i.e. the black box for $\sqrt n$ numbers can be itself reduced to an algorithm using a black box for sorting $n^{\frac{1}{4}}$ numbers and so on.
Kaveh
CC BY-SA 3.0
2013-03-17T17:30:28.330Z
@Kaveh thanks. I made some changes and it seems to be fine now. Please let me know if more clarification is needed.
AmeerJ
CC BY-SA 3.0
2013-03-17T17:31:46.797Z
@JɛﬀE the post was edited a lot. I've described my algorithm which uses $n$ calls to the black box. (does it seem right to you?)
I'm trying to prove no algorithm can call it $o(n)$ times.
AmeerJ
CC BY-SA 3.0
2013-03-17T17:38:32.623Z
@Kaveh The main point of my edit was that comparisons are not important here. We are only interested in number of calls to black box. Please take a look at the answer by user14004. It looks like to be closely related to my question.
AmeerJ
CC BY-SA 3.0
2013-03-17T17:49:26.107Z
I think we can even get $O(\sqrt{n}\log n)$ using AKS's sorting network. Their network can be thought of as an instantiation of your model where the black box can sort blocks of size 2. Their algorithms uses $O(\log n)$ rounds, each round calling the 2-sorter $O(n)$ times. One "round" of $O(n)$ 2-sorters can be easily simulated with $O(\sqrt{n})$ $\sqrt{n}$-sorters.
Vinayak Pathak
CC BY-SA 3.0
2013-03-17T18:51:15.933Z
@VinayakPathak: Break up the input data into $2\sqrt{N}$ chunks of size $\sqrt{N}/2$, and then sort the chunks using the AKS network, after replacing each comparator with a $\sqrt{N}$-sorter.
Jeffε
CC BY-SA 3.0
2013-03-17T20:06:37.690Z
@JɛﬀE: Yes, great, that definitely looks simpler than my construction.
Vinayak Pathak
CC BY-SA 3.0
2013-03-17T20:33:29.620Z
I think you need to specify exactly what operations you are allowing to be performed on the numbers. In the original post it wasn't clear how you were merging the arrays. In the new one it is not clear how you find out which array an item belongs to if you don't use comparisons. If you are allowing comparisons then we can sort the numbers with 0 calls, just ignore the black box and directly sort the numbers. You have to say somehow that is not the case. The mentioned papers probably don't allow *any* operations on the numbers except the black box, but your algorithm is not so.
Kaveh
CC BY-SA 3.0
2013-03-17T20:36:07.310Z
@JɛﬀE, your comments can be an answer. :)
Kaveh
CC BY-SA 3.0
2013-03-18T16:42:38.103Z
@Kaveh: Upgraded.
Jeffε
<ds.algorithms><sorting><decision-trees>
Sorting using a black box
AmeerJ
# Sorting using a black box

(Asked by: username_0 on 2013-03-17)

Assume that we want to sort a list $S$ of $n$ real numbers.
Assume that we are given a black box that can sort $\sqrt n$ real numbers instantly.
How much advantage can we gain using this black box?

For example, can we sort the numbers with only $O(\sqrt n)$ calls to the black box?
The best algorithm that I have found uses $n$ calls to the black box.
But I haven't been able to improve it further.
Here is my algorithm which is similar to merge-sort:

First partition the list $S$ into $\sqrt n$ lists $s\_1, s\_2, ..., s\_{\sqrt n}$ with approximately $\sqrt n$ size.
Then use $\sqrt n$ calls to the black box to sort these lists.
Finally, merge the sorted lists using the black box as follows:

Put the smallest elements of the lists in a new list $L$,
then call the black box to sort it.
The number in $L[1]$ (first and smallest element of $L$) will be
the smallest number in $S$.
We can put it in the first place of the output list.  
Assuming the element has been chosen from $s\_j$,
we replace $L[1]$ with the second smallest element of sort list $s\_j$,
and again run the black box on it to compute the second smallest member of $S$.  
We continue till all the elements are sorted. The total number of black box calls for this part will be $n - \sqrt n$. Therefore overall the total number of calls will be $n$.

On the other hand, it looks like we should be able to obtain a lower-bound using the lower-bound on the number comparisons needed for sorting as follows:
We can implement the black box using $\sqrt n \lg \sqrt n = \frac{1}{2} \sqrt n \lg n$ comparisons.
If we can solve the problem with $o(\sqrt n)$ calls to the black box and merging in linear-time we can sort $n$ real numbers with $o(n \lg n)$ comparisons which is impossible.

I guess we could prove that $\Omega(n)$ is a lower-bound for the number of calls to the black box, since lots of comparisons using in the black box would be shared and therefore are recounted in our argument.

**UPDATE:** As the the other posts suggest, an $\sqrt n \lg n$ is also achievable.

**Tags:** ds.algorithms, sorting, decision-trees
> **Comments:**
> **username_1**: Isn't it obvious that this cannot be done in less than linear number of operations in the size of the input i.e. $N$? What do you mean by comparisons? You should probably be more specific about the model of computation you are using, e.g. [real RAM](http://en.wikipedia.org/wiki/Real_RAM) model.  
> **username_0**: Oh ... you're right. I meant the number of usages of the machine. You should only use the machine for comparisons. I'm updating the question.  
> **username_0**: To make my statement about comparisons more clear, I'd prove that if you use the machine less than $O(\sqrt N)$ times, I could sort $N$ numbers faster than $O(N log N)$. Because if I replace your imaginary machines with a real algorithm, say merge sort, each one requires a $\sqrt N log{\sqrt N } = 1/2 {\sqrt N} log N$ and thus the sorting is done in less than $\sqrt N * O(\sqrt N * log N) \approx O(N log N)$ which is not possible.  
> **username_1**: There seems to be a typo in your comment. Did you mean to say: "no algorithm using less than $\sqrt{N}$ calls to the machine can sort $N$ real numbers with less than $N\lg N$ comparisons"? ps: you should also be careful about the fact that the $N\lg N$ lower-bound only holds for comparison based sorting algorithms.  
> **username_1**: I edited the question for readability. Fill free to roll back or edit further. I am not sure what you mean by the last line though. ps: In a way, you are asking about a good self-reduction from sorting to itself. Note that we can also use a self-reduction recursively, i.e. the black box for $\sqrt n$ numbers can be itself reduced to an algorithm using a black box for sorting $n^{\frac{1}{4}}$ numbers and so on.  
> **username_0**: @Kaveh thanks. I made some changes and it seems to be fine now. Please let me know if more clarification is needed.  
> **username_0**: @JɛﬀE the post was edited a lot. I've described my algorithm which uses $n$ calls to the black box. (does it seem right to you?) I'm trying to prove no algorithm can call it $o(n)$ times.  
> **username_0**: @Kaveh The main point of my edit was that comparisons are not important here. We are only interested in number of calls to black box. Please take a look at the answer by user14004. It looks like to be closely related to my question.  
> **username_2**: I think we can even get $O(\sqrt{n}\log n)$ using AKS's sorting network. Their network can be thought of as an instantiation of your model where the black box can sort blocks of size 2. Their algorithms uses $O(\log n)$ rounds, each round calling the 2-sorter $O(n)$ times. One "round" of $O(n)$ 2-sorters can be easily simulated with $O(\sqrt{n})$ $\sqrt{n}$-sorters.  
> **username_3**: @VinayakPathak: Break up the input data into $2\sqrt{N}$ chunks of size $\sqrt{N}/2$, and then sort the chunks using the AKS network, after replacing each comparator with a $\sqrt{N}$-sorter.  
> **username_2**: @JɛﬀE: Yes, great, that definitely looks simpler than my construction.  
> **username_1**: I think you need to specify exactly what operations you are allowing to be performed on the numbers. In the original post it wasn't clear how you were merging the arrays. In the new one it is not clear how you find out which array an item belongs to if you don't use comparisons. If you are allowing comparisons then we can sort the numbers with 0 calls, just ignore the black box and directly sort the numbers. You have to say somehow that is not the case. The mentioned papers probably don't allow *any* operations on the numbers except the black box, but your algorithm is not so.  
> **username_1**: @JɛﬀE, your comments can be an answer. :)  
> **username_3**: @Kaveh: Upgraded.  

---

## 3 answers

### Answer by username_5 on 2013-03-17. Score: 16 | Accepted answer

It's possible to sort with $O(\sqrt n\log n)$ calls to the black box and no comparisons.
First, consider the following balanced partitioning problem: given $m$ elements $A[1..m]$ (where $\sqrt n \le m \le n$), partition them into two groups, the smallest of size at least about $m/4$, so that all elements in the first group are smaller than all elements in the second group.  This can be done with $O(m/\sqrt n)$ calls to the black box.  (I'll describe that later.)  Then use quicksort with this partitioning algorithm:
def qsort(A[1..m]):
   if m < sqrt(n): sort A with one call to the black box
   else:
     Partition A[1..m] into two groups as described above.
     Recursively qsort the first group.
     Recursively qsort the second group.

Assuming each partition step takes $O(m/\sqrt n)$ calls to the black box, the above algorithm, given input $A[1..n]$, will make $O(\sqrt n\log n)$ calls to the black box, because the recursion tree has depth $O(\log n)$ and each level of the tree has a total of $O(n/\sqrt n) = O(\sqrt n)$ calls to the black box.
Do the partitioning step as follows:
def partition(A[1..m]):  (where sqrt(n) <= m <= n)
   Divide A into m/sqrt(n) groups of size sqrt(n) each.
   Sort each group with one call to the black box per group.
   Sort the medians of the groups with one call to the black box.
   (Note the number of groups is less than sqrt(n), because m <= n.)
   Let X be the median of the medians.
   Partition all m elements around X, using the black box as follows:
      For each group G, let Y be its median:
        Call the black box once on (G - {Y}) union {X}.
        (This gives enough information to order all elts w.r.t. X.)

> **Comments:**
> **username_2**: In the last step of the algorithm partition(): "Partition all m elements around X", won't this use m additional comparisions?  
> **username_5**: See the line just following the algorithm, it explains how to do that step.  I'll edit it to make that clearer.  

---

### Answer by username_4 on 2013-03-17. Score: 25

I think your question was addressed in Beigel and Gill's paper
"[Sorting n objects using k-sorter](http://doi.ieeecomputersociety.org/10.1109/12.53587)" from 1990 and the abstract of the paper says it all:

> A k-sorter is a device that sorts k objects in unit time. The complexity of an algorithm that uses a k-sorter is defined as the number of applications of the k-sorter. In this measure, the complexity of sorting n objects is between $\frac{n \log n}{k \log k}$ and $\frac{4n \log n}{k \log k}$, up to first-order terms in n and k.

> **Comments:**
> **username_0**: Thank you. I couldn't find the paper. Can you provide the link to the paper or its proof?  
> **username_5**: [link to paper](http://scholar.google.com/scholar?cluster=5722195084700676122&hl=en&as_sdt=0,5)  
> **username_1**: Also on [citeseerx](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.7281).  
> **username_3**: Note that when $k=\sqrt{n}$, Beigel and Gill's bound is $\Theta(\sqrt{n})$.  

---

### Answer by username_3 on 2013-03-18. Score: 12

It is possible to sort obliviously with $O(\sqrt{n}\log n)$ calls to the black box, each applied to a contiguous subarray of the original input.  The algorithm never touches the input data except through black-box calls. In particular, the same sequence of black-box calls is only a function of $n$, not the actual input data (hence "oblivious").
Here is a sketch of a simpler algorithm, which uses a black box that sorts subarrays of size $k$ instead of just $\sqrt{n}$.  The total number of calls to the black box is roughly $2(n/k)^2$.  For notational simplicity, assume that $k$ is even and $2n/k$ is an odd integer.
BlockBubbleSort(X[0..n-1], k):
   m = floor(n/k)
   for i = 1 to m
      for j = 0 to m-1
          BlackBoxSort(X[j*k .. (j+1)*k-1])
      for j = 0 to m-1
          BlackBoxSort(X[j*k + k/2 .. (j+1)*k + k/2 - 1])

Here is a diagram of the algorithm for $n=18$ and $k=4$.  Data travels from left to right; each box is a $k$-sorter.

As the figure hopefully suggests, this algorithm breaks the input array into chunks of size $k/2$, and then applies bubblesort to the chunks, using the $k$-sorter in place of a compare-exchange operation.  Correctness follows by observing that the network correctly sorts any array of 0s and 1s.
As @VinayakPathak's comment suggests, the $O((n/k)^2)$ bound can be reduced by replacing bubblesort with a different sorting network.  For example, Batcher's even-odd mergesort reduces the number of black-box calls to $O((n/k)\log^2(n/k)) = O(\sqrt{n}\log^2 n)$, and the AKS sorting network reduces it to $O((n/k)\log (n/k)) = O(\sqrt{n}\log n)$.  This last algorithm matches Neal's non-oblivious algorithm up to (large!!) constant factors.

> **Comments:**
> **username_0**: thanks. Can a $\Omega(\sqrt n\ lg(n))$ lower bound be proved?  
> **username_3**: No, Biegel and Gill's paper implies an upper bound of $O(\sqrt{n})$.  
> **username_6**: +1 for that nice picture! I may be mistaken but it seems to me that it is not entirely correct (correct me if I'm wrong). Assuming the output is in ascending order, if the smallest element is in the last position there is no "path" for it to "travel" to the first position. Changing "for i = 1 to m" to "for i = 1 to m+1" seems to correct this, although it might introduce some unnecessary overhead.  
> **username_3**: @George Oops, you're right; I need one more layer!  

---

