Sorting using a black box 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.
I think your question was addressed in Beigel and Gill's paper
"Sorting n objects using k-sorter" 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.