Radix sort is a non-comparative number sorting algorithm that sorts information with number keys by grouping keys by the individual digits that share constant important position and value. A numeration system is needed, however as a result of integers can represent strings of characters and specially formatted floating point numbers, radix sort isn’t restricted to integers.


1) for i ? 1 to d;
2) do use a stable sort to sort Array A on digit i // counting sort will do the job//

First for each value of the input array we put the value of “1” on the key-th place of the temporary array as explained on the following diagram.

If there are repetition values within the input array we tend to increment the corresponding value within the temporary array. once “initializing” the temporary array with one pass (with linear complexity) we are able to sort the input.


Radix-Sort(A, d)
//It works same as counting sort for d number of passes.
//Each key in A[1..n] is a d-digit integer.
//(Digits are numbered 1 to d from right to left.)
    for j = 1 to d do
        //A[]-- Initial Array to Sort
        int count[10] = {0};
        //Store the count of "keys" in count[]
        //key- it is number at digit place j
        for i = 0 to n do
         count[key of(A[i]) in pass j]++

        for k = 1 to 10 do
         count[k] = count[k] + count[k-1]

        //Build the resulting array by checking
        //new position of A[i] from count[k]
        for i = n-1 downto 0 do
         result[ count[key of(A[i])] ] = A[j]
         count[key of(A[i])]--

        //Now main array A[] contains sorted numbers
        //according to current digit place
        for i=0 to n do
          A[i] = result[i]

    end for(j)
end func
Radix Sort