Counting sort runs on relatively smaller set of input.
Counting sort calculates, for every element in array - X, the number of elements which are lesser than - X. It then use this information to put *X* directly into its position in sorted array.

Selection sort takes two additional array.

- One for result, the sorted array
- other for temporary storage, where size equals to the maximum number on input array.

Its interesting to note that this algorithm is not a comparison sort. You will not see any comparison in code. This algorithm uses elements values to index into array.

## Count Sort Algorithm

- First iterate on input array, and calculate each number occurence in the 2nd additional array (lets call it C).
- After the iteration, The array-C’s index will denote the input number, and the value contains how many times the number comes in original array. In the image above, see part-a.
- Run one more iteration on array-c. And, accumulate the sum. See above image, part-b
- Now iterate equal to length of original array (from last index to 0):
- For the number in original array, use it as index in array-C, which will give you its position in sorted array
- Put this number in sorted array at position told by array-c
- Decrement this value from array-c by 1

- At the end, we will get sorted array.

See the code here:

```
public class CountSort {
private int[] arr;
public CountSort(int[] arr) {
this.arr = arr;
}
/**
* Count sort, max value-k
* @param k, the max value in array
*/
public int[] doSort(int k) {
int[] c = new int[k+1];
//count number of occurence
for (int i=0; i<this.arr.length; i++) {
c[this.arr[i]] ++;
}
//accumulate
for (int i=1; i<c.length; i++) {
c[i] += c[i-1];
}
int[] result = new int[this.arr.length];
//put the number to its designated place
for (int i=this.arr.length-1; i>=0; i--) {
result[c[this.arr[i]]-1] = this.arr[i];
c[this.arr[i]] --;
}
return result;
}
}
```

## Key Points

- It is not a comparison sort.
- It is a stable sort.
- This uses 2 additional arrays.
- It is used for relatively smaller set of numbers.
- The maximum number in array should be order of size of array. Example: this algorithm is good for sorting age of people.
- Performance is very good. its time complexity is
*O(n + k) ~= O(n)*

## Runtime complexity

The algorithm runs on time complexity of *O(n + k) ~= O(n)* in worst/average case.