CODEWITHSUNDEEP
algorithmsorting
newSolar
newSolar

Reputation: 81

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

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?

Upvotes: 6

Views: 145

Answers (2)

Lior Kogan
Lior Kogan

Reputation: 20648

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.

Upvotes: 2

Alan Tam
Alan Tam

Reputation: 2057

Zero. You can write a new function that sorts n^2 numbers, and you don't need to call F(). Is this cheating? I don't think so. It completely depends on what extra you are allowed to do except calling F().

You can partition n^2 numbers into n groups of n numbers and call F() on the each group, and then do a merging on n lists of n numbers. This is also a plausible solution, except you may still call it cheating.

There can be more specific solutions if you want to further put constraints to the question, but you have to spell out these constraints explicitly.

Upvotes: 0

Related Questions