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

Steps

  1. Construct a working array C that has size equal to the range of the input array A.
  2. Iterate through A, assigning C based on the number of times x appeared in A.
  3. 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.
  4. 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

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/d27c47e4-b8aa-4c81-bce5-f02f01a58c7c/Untitled.png

Auxiliary Space: O(n+k) Time Complexity: Worst-case: O(n+k), Best-case: O(n), Average-case O(n+k)