# 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*based on the number of times x appeared in*A*. - Transform
*C*into an array where*C*refers to the number of values ≤ x by iterating through the array, assigning to each*C*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*by assigning*B*[*C*[*A*]] to*A*, and decrementing*C*[*A*] 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)`

Found a mistake? Have a question or improvement idea?
Let me know.

Table Of Contents