# Sorting 1 million integers from 1 to 9 using Java code

For large inputs Java `Collections.sort()`

uses TimSort which runs in **O (n log (n))** . If you want it to run faster, let's say linear time than you should use a comparison based sorting algorithm.

Since your range of integers is much less than the number of items to sort, this is an ideal use for Counting Sort .

Be `k = 9`

(range 1 to 9) and `N = 1 million`

. Your running time will be **O (k + N)** .

source to share

Login: [1,2,5,4,7,8,9,6,5,4,2,3,6,5,8]

Output: [1,2,2,3,4,4,5, 5,5,6,6,7,8,8,9]

This can be solved in O (n) time with O (k) space.

Since the given range is 9, we can create a 9 + 1 array, where each index will store an occurrence of a number in the input array

TempArray = [0 1 2 1 2 3 2 1 2 1] Index 0 1 2 3 4 5 6 7 8 9

All you have to do is read the tempArray and fill the data back into the input.

The value at index 1 is 1, so we'll only add one item.

the value at index 2 is 2, so we'll add two times two.

the value at index 3 is 1, so we'll only add three once.

the value at index 4 is 2, so we'll only add four two times ...

this way you can override the original array.

T (O (n)) S (O (k))

Let me know if you have any confusion.

here is the C # code for the same:

```
int[] input = new int[15] { 1, 2, 5, 4, 7, 8, 9, 6, 5, 4, 2, 3, 6, 5, 8 };
int k = 9;
int[] temp = new int[k + 1];
for (int index = 0; index < input.Length; index++)
{
temp[input[index]]++;
}
int i = 0; // used for input index
for (int index = 0; index < temp.Length; index++)
{
while (temp[index]-- != 0) // redusing count value after updating the index into input array
input[i++] = index;
}
for (int index = 0; index < input.Length; index++)
{
Console.Write(" {0} ", input[index]);
}
```

source to share