Search code examples
sortingradix-sortarray-algorithms

Can someone explain to me radix-sort?

I am trying to implement radix-sort in javascript. However, I do not know how to do radix-sort! I have this pseudocode (from Introduction to Algorithms):

RADIX-SORT(A, d)
    for i = 1 to d
        use a stable sort to sort array A on digit i

however, when it says A on digit i, what is the meaning of that?

Solution

  • In Radix sort, elements are sorted according to i^th digit. It starts sorting array A by looking at digit 1, then 2, ... upto digit d.

    For example: A = {423, 241, 732}

    Iteration 1 (i=1): A = {241,732,423}

    Iteration 2 (i=2): A = {423,732,241}

    Iteration 3 (i=3): A = {241,423,732} --sorted**

    This takes linear time to sort an array of n elements (depends on the stable sort used inside). This does the sorting in O(n+d) time, where d is number of digits in an element.

    And we could use any stable sort(counting sort or any other) to sort the elements.