Counting Sort

// Counting sort

#include<bits/stdc++.h>
#define endl "\n"
using ll = long long;

using namespace std;

void counting_sort(vector<int> &vec) {
    int mn = *min_element(vec.begin(), vec.end());
    int mx = *max_element(vec.begin(), vec.end());

    int offset = (mn < 0) ? (mn*-1) : 0;
    for(int i=0; i<vec.size(); i++) vec[i] += offset;

    int freq[mx+offset+1] = {0};
    for(int i=0; i<vec.size(); i++) freq[vec[i]]++;

    int index = 0;
    for(int elem = mn+offset; elem<=mx+offset; elem++) {
        while(freq[elem]--) {
            vec[index++] = elem;
        }
    }
    for(int i=0; i<vec.size(); i++) vec[i] -= offset;
}

int main() {
    vector<int> ara = {-5, 10, 9, 8, -5, -2, 5, 13, 10};
    counting_sort(ara);

    for(auto u:ara) cout << u << " ";

    return 0;
}