Counting Sort

#include <bits/stdc++.h>

using namespace std;

int main() {
    std::ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    // scanf("%d", &n);
    int cnt[201] = {}; // -100 <= x <= 100;   0-> -100, 1-> -99, 100->0, 200->100
    int shift = 100;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        // scanf("%d", &x);
        cnt[x + shift]++;
    }

    for (int x = -100; x <= 100; ++x) {
        for (int i = 0; i < cnt[x + shift]; ++i) {
            cout << x << " ";
            // printf("%d ", x);
        }
    }

    return 0;
}

// Counting Sort
// Time Complexity O(n + interval)
// Memory Complexity O(interval)
/*                  x
5 4 5 3 2 2 5 4 2 1


       0  1  2  3  4  5
cnt = {0, 1, 3, 1, 2, 3}
*/