# Efficient way to sort large set of numbers

I have to sort a set of 100000 integers as a part of a programming Q. The time limit is pretty restrictive, so I have to use the most time-efficient approach possible.

My current code -

``````#include<cstdio>
#include<algorithm>
using namespace std;

int main() {
int n,d[100000],i;
for(i=0;i<n;++i) {
scanf("%d",&d[i]);
}
sort(d,d+n);
....
}
``````

Would this approach be more efiicient?

``````int main() {
int n,d[100000],i;
for(i=0;i<n;++i) {
scanf("%d",&d[i]);
sort(d,d+i+1);
}
....
}
``````

What is the most efficient way to sort a large dataset?

Note - Not homework...

-
I am pretty sure your 2nd approach will be slower - but why don't you just test it? – Doc Brown Nov 2 '12 at 7:38
@DocBrown I did, both are pretty inefficient. However the latter's apparently a bit faster... Strange, yes. – 7Aces Nov 2 '12 at 8:21
let me guess - you are not measuring the speed of the sort, you are measuring the speed of the `scanf` – Doc Brown Nov 2 '12 at 11:09
@Aces: in that case, just create an array and count the number of occurrences of each value. That will give you linear runtime. – kevin cline Nov 5 '12 at 19:12
Did you write the sort function? If in your experience both methods are equally slow then your sort is at least O(n^2). It doesn't look efficient. You should use the standard sort from the C library. – Florian F Nov 26 '15 at 15:44

For maximum efficiency you only want to do the sort once, so version 2 is definitely not the way to go.

An alternative to just storing the numbers in an array in the order they are read and then sorting, is to use a data structure that will sort itself as each number is added, such as a (red/black) binary tree or a skip list. This will require additional memory for the pointer links between items, but may be faster - only an experiment can determine that.

However, efficiency of any particular sorting algorithm can often depend greatly on the initial order of the items - e.g. already sorted / inverse sorted / random.

-

If you want to sort time-efficient and it is guaranteed that your elements are numbers, then go for `Radix-Sort`. It is sorting your Dataset in `O(a*n)`, a is the length of the longest/biggest number. 10 would get you a=2, 200 would get you a=3, 2*10^(100) would get you a=1000 and so on.

Quicksort can sort in O(log(n)*n) what is good, but can suck and be as bad as Bubblesort and sort your Dataset in Theta(n²).

Can you tell us how much time you have to sort it, or how much time you have in general?

-
The OP posted this question in November of 2012. I'm fairly sure the question, constraints, and issues but memories in the past. Asking for clarification on them is likely not going to come up with any additional information. – user40980 Dec 24 '15 at 21:07
Ouh, just have seen it on the front on the App.... Well, sorry for that – Sparkay Dec 24 '15 at 21:09