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 timesSorted 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**