RADIX SORT

• Radix sort sorts the elements by processing its individual digits. Radix sort processing the digits either by LSD(Least Significant Digits) method by most processing digits (MSD) method. 

      Least Significant Digit(LSD):
         

• It is the lowest digit in a number,located at the far right of the string.          

      Example
          
                  
      Most Significant Digit:

• Most Significant Digit is the far left in a string of digit.

     Example
     
                      

• Radix sort is clever and intuitive little sorting algorithm radix sort puts the elements in order by comparing the digits of the numbers. 

EXAMPLE

Consider the following numbers, 

                 

• We should starting by comparing  and ordering the one's digits.
• Radix sort is generalized from bucket sort. it can be performed using buckets from 0 to 9. 

                 

• In second pass the numbers are arranged according to the next least significant bit and so on.This process is repeated until it reaches the most significant bits of all numbers.

         

• Now the sub-lists are created again, this time based on the ten's digit.

             

• Now the sub-list are created according to the hundred's digit.

                   

After Radix Sort:

           

Complexity:

• Worst case:O(n)
• Best case:O(n)
• Average case:O(n)

Advantages:

• Radix sort is very simple.
• A computer can do it fast.
• Radix sort is in fact one of the fastest sorting algorithm for numbers or strings of letters.

Disadvantages:

• Radix sort can be slower than some other algorithms such as Quick Sort and Merge Sort.
• It can take-up more space than other sorting algorithms,since in addition to the array that will be sorted.

                            ******