## C# Implementation

```
public class CountingSort
{
public static void SortCounting(int[] input, int min, int max)
{
var count = new int[max - min + 1];
var z = 0;
for (var i = 0; i < count.Length; i++)
count[i] = 0;
foreach (int i in input)
count[i - min]++;
for (var i = min; i <= max; i++)
{
while (count[i - min]-- > 0)
{
input[z] = i;
++z;
}
}
}
public static int[] Main(int[] input)
{
SortCounting(input, input.Min(), input.Max());
return input;
}
}
```

## Counting Sort Basic Information

Counting sort is an integer sorting algorithm for a collection of objects that sorts according to the keys of the objects.

**Steps**

- Construct a working array
*C*that has size equal to the range of the input array*A*. - Iterate through
*A*, assigning*C*[x] based on the number of times x appeared in*A*. - Transform
*C*into an array where*C*[x] refers to the number of values ≤ x by iterating through the array, assigning to each*C*[x] the sum of its prior value and all values in*C*that come before it. - Iterate backwards through
*A*, placing each value in to a new sorted array*B*at the index recorded in*C*. This is done for a given*A*[x] by assigning*B*[*C*[*A*[x]]] to*A*[x], and decrementing*C*[*A*[x]] in case there were duplicate values in the original unsorted array.

**Example of Counting Sort**

**Auxiliary Space:** `O(n+k)`

**Time Complexity:** Worst-case: `O(n+k)`

, Best-case: `O(n)`

, Average-case `O(n+k)`

## Psuedocode Implementation

Constraints:

- Input (an array to be sorted)
- Number of element in input (n)
- Keys in the range of
*0..k-1*(k) - Count (an array of number)

Pseudocode:

```
for x in input:
count[key(x)] += 1
total = 0
for i in range(k):
oldCount = count[i]
count[i] = total
total += oldCount
for x in input:
output[count[key(x)]] = x
count[key(x)] += 1
return output
```