Counting Sort

1. Take a count array to store the count of each unique object.
2. Modify the count array such that each element at each index stores the sum of previous counts.
3. Output each object from the input sequence followed by decreasing its count by 1.

Time Complexity: O(n+k) where n is the number of elements in input array and k is the range of input. Auxiliary Space: O(n+k)

Noted:

1. Counting sort is efficient if the range of input data is not significantly greater than the number of objects to be sorted.
2. It is not a comparison based sorting. It's running time complexity is O(n) with space proportional to the range of data.
3. Can only be applied to numeric array.

vector<int> countSort(vector<int> &arr) {
    vector<int> count(arr.size()+1, 0);

    // Store count of each element
    for (auto num: arr) {
        count[num]++;
    }

    // Change count[i] so that count[i] now contains actual
    // position of this character in output array
    for (i = 1; i <= arr.size(); ++i) {
        count[i] += count[i-1];
    }

    // Build the output array
    vector<int> output;
    for (i = 0; i < arr.size(); ++i) {
        int index = count[arr[i]] - 1;
        output[index] = arr[i];
        count[arr[i]] -= 1;
    }

    return output;
}