#include <iostream>
using namespace std;
 
void CountingSort(int from[], int to[], int len, int maxval) {
    int *count = new int[maxval + 1];
 
    for (int i = 0; i < (maxval + 1); i++)
        count[i] = 0;
    for (int j = 0; j < len; j++)
        count[from[j]]++;
 
    int *topidx = new int[maxval + 1];
    topidx[0] = count[0];
    for (int i = 1; i < (maxval + 1); i++)
        topidx[i] = count[i] + topidx[i - 1];
    delete[] count;
 
    for (int j = len - 1; j >= 0; j--) {
    	int value = from[j];
        topidx[value]--;
        to[topidx[value]] = value;
    }
    delete[] topidx;
}
 
int main()
{
    int v[10] = {9, 0, 3, 4, 1, 2, 7, 8, 5, 6};
    int u[10];
 
    CountingSort(v, u, 10, 9);
 
    for (int i = 0; i < 10; i++)
        std::cout << u[i] << ' ';
 
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdm9pZCBDb3VudGluZ1NvcnQoaW50IGZyb21bXSwgaW50IHRvW10sIGludCBsZW4sIGludCBtYXh2YWwpIHsKICAgIGludCAqY291bnQgPSBuZXcgaW50W21heHZhbCArIDFdOwoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgKG1heHZhbCArIDEpOyBpKyspCiAgICAgICAgY291bnRbaV0gPSAwOwogICAgZm9yIChpbnQgaiA9IDA7IGogPCBsZW47IGorKykKICAgICAgICBjb3VudFtmcm9tW2pdXSsrOwoKICAgIGludCAqdG9waWR4ID0gbmV3IGludFttYXh2YWwgKyAxXTsKICAgIHRvcGlkeFswXSA9IGNvdW50WzBdOwogICAgZm9yIChpbnQgaSA9IDE7IGkgPCAobWF4dmFsICsgMSk7IGkrKykKICAgICAgICB0b3BpZHhbaV0gPSBjb3VudFtpXSArIHRvcGlkeFtpIC0gMV07CiAgICBkZWxldGVbXSBjb3VudDsKCiAgICBmb3IgKGludCBqID0gbGVuIC0gMTsgaiA+PSAwOyBqLS0pIHsKICAgIAlpbnQgdmFsdWUgPSBmcm9tW2pdOwogICAgICAgIHRvcGlkeFt2YWx1ZV0tLTsKICAgICAgICB0b1t0b3BpZHhbdmFsdWVdXSA9IHZhbHVlOwogICAgfQogICAgZGVsZXRlW10gdG9waWR4Owp9CgppbnQgbWFpbigpCnsKICAgIGludCB2WzEwXSA9IHs5LCAwLCAzLCA0LCAxLCAyLCA3LCA4LCA1LCA2fTsKICAgIGludCB1WzEwXTsKCiAgICBDb3VudGluZ1NvcnQodiwgdSwgMTAsIDkpOwoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgMTA7IGkrKykKICAgICAgICBzdGQ6OmNvdXQgPDwgdVtpXSA8PCAnICc7CgogICAgcmV0dXJuIDA7Cn0=