Sort n ^ 2 numbers only with a function that can sort n numbers

Question

There is a function F () that can sort any n numbers, now there are n ^ 2 numbers that need to be sorted, how many times do you need to call F (), at least do you need to? (you can only call F ()). I thought up a method similar to bubble type about calling O (n ^ 2). Is there a better way?

Answer 1

You will need steps n (2n-1) (in the worst case). Here is an intuitive explanation:

Suppose there are 4 sorted groups of size (n / 2). Let us call them A, B, C, D. We also assume that each of these groups is sorted, that the initial input vector is DCBA and that the final sorted vector must be ABCD.

In each individual operation, we can change the order of two groups (for example, change BA to AB).

DCBA sorting requires the following steps:

DCBA → CDAB (2 steps) → CADB (1 step) → ACBD (2 steps) → ABCD (1 step)

Total steps: 6 = 4 * 3/2

Now we 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), you need x (x-1) / 2 steps (each step sorts n consecutive elements).

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

---

Edit:

What if one n-sorter (F) can sort arbitrary elements (not necessarily sequential)?

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

Take a look at this recent article by Shea, Jan, and Wag :

In this paper, we propose an n-dimensional merge algorithm that generalizes the odd-even merge using n-sorters as the main building blocks, where n (≥ 2) is simple. Based on this merge algorithm, we also offer a sorting algorithm. For input values ​​N = n ^ p, p + ⌈n / 2⌉ × p (p-1) / 2 steps are necessary. The complexity of the sorting network by the total number of n-sorters is estimated. Closed form expression for The number of sorters is also determined.

Answer 2

Zero. You can write a new function that sorts the numbers n^2 , and you do not need to call F() . This is a lie? I do not think so. It completely depends on what else you are allowed to do, except for calling F() .

You can divide the numbers n^2 into n groups of n and call F() in each group, and then merge into n lists of numbers n . This is also a plausible decision, except that you can still call it a hoax.

There may be more specific solutions if you want to add restrictions to the question, but you must explicitly specify these restrictions.