Counting Sort

Counting sort is a sorting algorithm that sorts the elements of an array by counting the frequency of each distinct element in the array.
The frequencies are stored in a frequency array. Sorting is done by calculating the position of elements from the index values of frequency array.

Input array:     12 2 3 4 2 3 6 8 4 5
Range of input array is 0 ~12 (min is 0 and max is 12)
Create a frequency array (size = max +1)
Frequency array: 0 0 2 2 2 1 1 0 1 0 0 0 1
Scan the frequency array from beginning and output the index values frequency times 
Sorted array:    2 2 3 3 4 4 5 6 8 12

Analysis:
Time complexity: O (n +k)
Space complexity: O (k)
where k the range of values and n is the number of values in the input array

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void counting_sort(vector<int>& v) {
  // find the max value so that freq array can be created
  auto max_val = max_element(begin(v), end(v));
  vector<int> freq(*max_val + 1);

  // find frequency
  for (int i = 0; i < v.size(); i++)
    freq[v[i]]++;

  // output sorted values from frequency table
  int k = 0;
  for (int i = 0; i < freq.size(); i++) {
    if (freq[i] > 0) {
      for (int j = 0; j < freq[i]; j++)
        v[k++] = i;
    }
  }
}
int main() {
  vector<int> v = {2, 3, 4, 2, 3, 6, 8, 4, 5};

  counting_sort(v);

  for (auto val : v)
    cout << val << " ";
  cout << endl;

  return 0;
}

2 2 3 3 4 4 5 6 8

References