sort n^2 numbers only with the function that can sort n numbers

Question

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?

Answer 1

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

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.

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

sorting DCBA requires the following steps:

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

Total steps: 6 = 4*3/2

Now support that you need to sort FEDCBA:

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

Total steps: 15 = 6*5/2

And so on....

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

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

---

Edit:

What if a single n-sorter (F) can sort arbitrary elements (not necessarily consecutive)?

This turns out to a research-level problem related to sorting networks. See also here.

Take a look at this recent paper by Shi, Yan, and Wagh:

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.