<p>You'll need n(2n-1) steps (worst case). Here is an intuitive explanation:</p>

<p>Suppose there are 4 sorted groups of size (n/2) each. Let's call them A,B,C,D.
Also suppose that each of these groups is sorted, that the initial input vector is DCBA and that the final sorted vector should be ABCD.</p>

<p>In each single operation we can change the order of 2 groups (e.g. change BA to AB).</p>

<p>sorting DCBA requires the following steps:</p>

<p>DCBA --> CDAB (2 steps) --> CADB (1 step) --> ACBD (2 steps) --> ABCD (1 step)</p>

<p>Total steps: 6 = 4*3/2</p>

<p>Now support that you need to sort FEDCBA:</p>

<p>FEDCBA --> EFCDAB (3 steps) --> ECFADB (2 steps) --> CEAFBD (3 steps) --> CAEBFD (2 steps) --> ACBEDF (3 steps) --> ABCDEF (2 steps)</p>

<p>Total steps: 15 = 6*5/2</p>

<p>And so on....</p>

<p>To sort x blocks of size (n/2) each you'll need x(x-1)/2 steps (each step sorts n consecutive elements).</p>

<p>n² elements are 2n * (n/2) blocks, so you'll need (2n)(2n-1)/2 = n(2n-1) steps.</p>

<hr>

<p><strong>Edit:</strong></p>

<p><strong>What if a single n-sorter (F) can sort arbitrary elements (not necessarily consecutive)?</strong></p>

<p>This turns out to a research-level problem related to <a href="https://en.wikipedia.org/wiki/Sorting_network" rel="nofollow">sorting networks</a>. See also <a href="https://mitpress.mit.edu/sites/default/files/Chapter%2027.pdf" rel="nofollow">here</a>.</p>

<p>Take a look at this <a href="http://arxiv.org/pdf/1407.0961v1.pdf" rel="nofollow">recent paper by Shi, Yan, and Wagh</a>:</p>

<blockquote>
  <p>In this work, we propose an n-way merging algorithm, which generalizes
  the odd-even merge by using n-sorters as basic building blocks, where
  n (≥ 2) is prime. Based on this merging algorithm, we also propose a
  sorting algorithm. For N = n^p input values, p + ⌈n/2⌉ × p(p−1)/2
  stages are needed. The complexity of the sorting network is evaluated
  by the total number of n-sorters. The closed form expression for the
  number of sorters is also derived.</p>
</blockquote>
sort n^2 numbers only with the function that can sort n numbers
<p>There is a function F() that can sort any n numbers, now there are n^2 numbers need to sort, how many times of calling F() you need at least ? (you can only call F() ).
I thought out a method like bubble sort, about O(n^2) times calling. Have any better way?  </p>