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)`

This modified text is an extract of the original Stack Overflow Documentation created by following contributors and released under CC BY-SA 3.0

This website is not affiliated with Stack Overflow