Here’s the problem:

————-

Given the list of numbers, you are to sort them in non decreasing order.

**Input**

t – the number of numbers in list, then t lines follow [t <= 10^6].
Each line contains one integer: N [0 <= N <= 10^6]
**Output**

Output given numbers in non decreasing order.

Example

Input:

5

5

3

6

7

1

Output:

1

3

5

6

7

—————–

As you probably can guess the main challenge here is the speed at which you can process and sort the input. My solution was to simply create an empty array, and increment each position according to the numbers that were given as input. After that I would only need to traverse the array once outputing all the respective numbers. It worked.

```
#include <stdio.h>
int array[1000001] = {0};
int main(){
int i,j;
scanf("%d",&j);
int x;
for (i=0;i<j;i++){
scanf("%d",&x);
array[x]++;
}
for (i=0;i<1000001;i++){
while(array[i]>0){
printf("%dn",i);
array[i]--;
}
}
return 0;
}
```

shubhamI am not understanding the working of following code:

for (i=0;i<j;i++){

scanf("%d",&x);

array[x]++;

}

will u please explain how array[x]++ is working here.

shubhamOh! i got it

it is just increasing the indices value….

pushpakwithout swapping how did it worked.

and reversing it didn’t get that?

gautam1. Won’t there be garbage values to some values for ‘x’? if the value is not inputted?

2. what if a number occurs twice ?

narendra jaggiYou’ve got to be kidding me!!! Tried with merge sort quick sort,Java’s inbuilt sort but it didn’t worked!!

Finally solved that too with easiest solution I can think of. Taken only 2.12 secs when the limit is 5 secs

Nikhil KhetanI tried doing the same thing in cpp, but its not working.

#include

using namespace std;

int main(){

int A[1000001]={0};

int n;

cin >> n;

int a;

while(n–){

cin >> a;

A[a]= A[a]+1;

}

int i=0;

while(i0){

cout << i << endl;

A[i]–;

}

i++;

}

return 1;

}

avishekuse scanf and printf instead of cin and cout

Ankit VermaThis code is good for quickly sorting values but this code fails when two or more same elements are entered in the array so don’t rely on this code take use of merge or heap sort