## Best sort

General chat, humour, riddles, logic/lateral/word puzzles...
S_r
Posts: 32
Joined: Thu Aug 10, 2017 5:37 am

### Best sort

Let there be a million numbers from one to million randomly placed in array, what is the minimum running time you can sort it in? I will reply at end. I really want everyone to give their answers
Last edited by S_r on Sun Dec 24, 2017 11:53 am, edited 2 times in total.
hk
Posts: 11122
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

### Re: Best sort

I don't know what lakh numbers are.
S_r
Posts: 32
Joined: Thu Aug 10, 2017 5:37 am

### Re: Best sort

Ten lakhs = a million. Sorry, I didn't know lakhs wasn't known to you
hk
Posts: 11122
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

### Re: Best sort

I don't think many members of Project Euler would have known what a lakhs is.
Be careful not to use purely local concepts.
v6ph1
Posts: 128
Joined: Mon Aug 25, 2014 7:14 pm

### Re: Best sort

I think it's possible for PE users to search unknown words - and there are many interesting number words. - Except the western concepts of thousand, million,...

@Topic:
Sorting is O(n*log n)
The factor depends on the architecture: lets assume 5.
1000000*20*5 = 100000000 = 10^8 Ops
Using a 4GHz CPU, we have 25ms.
hk
Posts: 11122
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

### Re: Best sort

v6ph1 wrote: Sun Dec 24, 2017 1:25 pm I think it's possible for PE users to search unknown words - and there are many interesting number words. - Except the western concepts of thousand, million,...
Yes that is possible of course.
However, I think it would be better to avoid such situations. (Unless you are on a linguistics site of course.
Or if those interesting number words are the subject of your post. At least you should be aware you are using words not common to your readers.)
hk
Posts: 11122
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

### Re: Best sort

v6ph1 wrote: Sun Dec 24, 2017 1:25 pm
@Topic:
Sorting is O(n*log n)
That depends on the degree of sorting and the sorting algoritm.
In general you can't say what the minimal time will be,
Svartskägg
Posts: 55
Joined: Thu Mar 29, 2012 12:55 pm
Location: Sweden

### Re: Best sort

S_r wrote: Sun Dec 24, 2017 9:19 am a million numbers from one to million
This can be interpreted as a million random numbers from the range 1 to 1000000 or as precisely all the numbers in the range.

320641_5486fc18ea1dcc4e9a8f29c7677a5c19 <-- my friend key
v6ph1
Posts: 128
Joined: Mon Aug 25, 2014 7:14 pm

### Re: Best sort

Unless a predictable randomness, O(n*log n) is the necessary time for sorting.
O(n) can only be achieved if the sequence has a defined order.

It doesn't matter if there are all the numbers in randomized order (I would assume from the description) or 1 million random numbers (up to 1million).

So my answer is 25ms (depending on the processing unit).
traxex
Posts: 66
Joined: Thu Oct 19, 2017 1:30 pm

### Re: Best sort

v6ph1 wrote: Mon Dec 25, 2017 12:13 am Unless a predictable randomness, O(n*log n) is the necessary time for sorting.
O(n) can only be achieved if the sequence has a defined order.
That is only true for comparison-based sorting algorithms. Both counting sort and radix sort could be used here since the range of values is known.

Whether O(n) is faster than O(n log n) in practice is another question. Million is a small number.
Technically, everyone is full of himself.
S_r
Posts: 32
Joined: Thu Aug 10, 2017 5:37 am

### Re: Best sort

We can take an array of size n+1 and simply assign a[n]=n and it will be sorted no comparison needed. Even if it is not from 1 to n and is within a range we can use a[n+minimum number]=n. Sorry for my english
S_r
Posts: 32
Joined: Thu Aug 10, 2017 5:37 am

### Re: Best sort

Tell me if it is something remarkable
traxex
Posts: 66
Joined: Thu Oct 19, 2017 1:30 pm

### Re: Best sort

The question is not completely silly. Sometimes sorting needs to be done in-place, because the array actually contains pairs (n,x) where the n is used for sorting and x is some data attached to it. Creating a new array that just contains the n values would not be useful, because what we really want is to have the x values sorted with respect to the n values.

Sorting a random permutation in-place can be done in O(n) time, resolving one cycle at a time.
Technically, everyone is full of himself.