• hashing 과 비슷한 개념을 가진 sorting 알고리즘
• 시간 복잡도: O(n+k) 로 k는 input 의 개수

#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    int arr[n];
    int cnt[n];
    int result[n];
    for(int i=0;i<n;i++){
        cin >> arr[i];
        cnt[i] = 0;
    }
    for(int i=0;i<n;i++){
        int index = arr[i];
        cnt[index]++;
    }
    
    for(int i=1;i<n;i++){
        cnt[i] += cnt[i-1];
    }
    
    for(int i=0;i<n;i++){
        int cnt_index = arr[i];
        int tmp = --cnt[cnt_index];
        result[tmp] = arr[i];
    }
    for(int i=0;i<n;i++){
        cout << result[i] << " ";
    }
    return 0;
}