Radix

include<iostream>

using namespace std;



// A utility function to get maximum value in arr[]

int getMax(int arr[], int n)

{

    int mx = arr[0];

    for (int i = 1; i < n; i++)

        if (arr[i] > mx)

            mx = arr[i];

    return mx;

}



// A function to do counting sort of arr[] according to

// the digit represented by exp.

void countSort(int arr[], int n, int exp)

{

    int output[n]; // output array

    int i, count[10] = {0};



    // Store count of occurrences in count[]

    for (i = 0; i < n; i++)

        count[ (arr[i]/exp)%10 ]++;



    // Change count[i] so that count[i] now contains actual

    //  position of this digit in output[]

    for (i = 1; i < 10; i++)

        count[i] += count[i - 1];



    // Build the output array

    for (i = n - 1; i >= 0; i--)

    {

        output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];

        count[ (arr[i]/exp)%10 ]--;

    }



    // Copy the output array to arr[], so that arr[] now

    // contains sorted numbers according to current digit

    for (i = 0; i < n; i++)

        arr[i] = output[i];

}



// The main function to that sorts arr[] of size n using