#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

void basic_count_sort(int * arr, int size) {
    // Find the largest element in our array
    int max = *std::max_element(arr, arr+size);
    
    // Make an array of that size, to store frequency of each element
    int * count = new int[max+1];
    
    //Initialize array to 0
    std::fill(count, count+max+1, 0);
    
    for(int i=0;i<size;++i) {
        ++count[arr[i]];
    }
    
    int currPos = 0;
    for(int i=0;i<max+1;++i) {
        if(count[i] != 0) {
            // Fill array with i, count[i] times
            // From array indices pos to pos+count[i]
            std::fill(arr + currPos, arr + currPos + count[i], i);
            currPos += count[i];
        }
    }
}

int main() {
    int arr[] = {100,100,100,5,3,3,6,5,4,2,4,5,5,4,2,1,1,1,100,1};
    int size = 20;
    basic_count_sort(arr, size);
    for(int i=0;i<size;++i)
        std::cout << arr[i] << " ";
}