void countSort(int arr[], int n, int exp)
{
    int *output=new int[n];
    int i, count[10] = {0};
    for (i = 0; i < n; i++)
        count[ (arr[i]/exp)%10 ]++;

    for (i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for (i = n - 1; i >= 0; i--)
    {
        output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
        count[ (arr[i]/exp)%10 ]--;
    }

    for (i = 0; i < n; i++)
        arr[i] = output[i];

    delete [] output;
}

void radix_sort(int arr[], int n)
{
    int m = max_array_value;

    for (int exp = 1; m/exp > 0; exp *= 10)
        countSort(arr, n, exp);
}
void counting_sort(int A[],int n, int k)
{
    int *B=new int[n];
    int *C=new int[k];

    for(int i=0; i<k; i++) C[i]=0;
    for(int i=0;i<n;i++) C[A[i]]++;
    for(int i=1; i<k; i++) C[i]=C[i]+C[i-1];
    for(int i=n-1; i>=0; i--) {
        B[--C[A[i]]]=A[i];
        }
    for(int i=0; i<n; i++) A[i]=B[i];
    delete [] B;
    delete [] C;
}