Photo credit to Chrissy Jarvis on Unsplash

Algorithm

1. Determine the value range of input values and create a count array of zeros of size equal to the range, as well as an output array of equal size to the input array.

2. Count the number of occurrences of each value, and store the number in the corresponding index in the count array.

3. Accumulate the values up to each index in the count array, and right-shift the entire array by one index.

4. Iterate over the input array again, and for each value x, look up its starting position in the auxiliary array. Place x in the corresponding position in the output array, and decrement the value in the auxiliary array at that position by 1

Implementation

Follow the steps in the algorithm above, and use the comments for reference. Spend some time following each step carefully and you will understand it.

void counting_sort(std::vector<int>& vec)
{
/* Determine the value range of input values */
    int max_val = *std::max_element(vec.begin(), vec.end());
    int min_val = *std::min_element(vec.begin(), vec.end());
    int range = max_val - min_val;

/* Create output array */
    std::vector<int> sorted_arr(vec.size());

/* Create an auxiliary array of zeros of size 
equal to the range of input values */
    std::vector<int> counts(range + 1, 0);

    for (int val : vec)
    {
/* Count the number of occurences of each value, 
store the number in the corresponding index */
        counts[val - min_val]++;
    }

/* Accumulate the values up to each index, 
and right-shift the entire array one index */
    for (int i = 1; i < counts.size(); i++) counts[i] += counts[i-1];

/* Iterate over the input array */
    for (int i = vec.size() - 1; i >= 0; i--)
    {
/* For each value X */
        int val = vec[i];
/* Look up its starting position in counts array */
        int pos = counts[val - min_val] - 1;
/* Place X in the corresponding position in the output array */
        sorted_arr[pos] = val;
/* Decrement the value in the auxiliary array at that position by 1 */
        counts[val - min_val]--;
    }

    std::copy(sorted_arr.begin(), sorted_arr.end(), vec.begin());
}

Time Complexity

The overall time complexity of the function is squared as shown below, where n is the size of the input array and k is the range of integers.

$$O(n+k)$$

The best-case scenario is when the array is sorted, or all values equal each other. On the other hand, the worst-case scenario occurs when all the input elements are distinct and evenly distributed across the range.

In both cases counting occurrences will take O(k) time, accumulating them will take O(k) time and sorting them will take O(n) time. Therefore, O(n+k) time in both cases.

Output

To test the algorithm a randomized array of N = ten million is passed into the array, and the range is printed to be N - 1.

user@computer:~$ g++ -o a sorting_algos.cpp 
user@computer:~$ ./a
-----------------------------
| Algorithm: Counting Sort  |
| Scenario:  Random Case    |
| Array:     Random         |
| Input N:   10000000
-----------------------------
Range: 9999999
Duration: 1 s
Duration: 1720 ms
Duration: 1720065 us
Duration: 1720065945 ns
No errors, array is sorted