//counting sort

#include <iostream>
#include <windows.h>
#include <time.h>

using namespace std;

const int N=256;

void counting(int A[])
{
    int*B=new int[N*N-1];
    int*C=new int[N];
    for(int i=0; i<N; i++)
        B[i]=0;
    for(int i=0; i<N; i++)
        B[A[i]]++;
    for(int i=1; i<N*N-1; i++)
        B[i]+=B[i-1];
    for(int i=N-1; i>=0; i--)
    {
        B[A[i]]--;
        C[B[A[i]]]=A[i];
    }
    for(int i=0; i<N; i++)
        A[i]=C[i];
    delete[]B;
    delete[]C;
}

int main()
{
    srand(time(NULL));
    int t[N];
    for(int i=0; i<N; i++)
        t[i]=rand()%65535;
    for(int i=0; i<N; i++)
        cout << t[i] << " ";
    cout << endl;
    cout << endl;
    counting(t);
    for(int i=0; i<N; i++)
        cout << t[i] << " ";
    return 0;
}