Radix Sort

It is a non-comparative integer sorting algorithm. It sorts data by grouping keys by the individual digits which share the same significant position and value. Think Tens, Hundreds, Thousands etc. Some pointers about Radix Sort:

  • Even though it is an integer sorting algorithm, it is not restricted just to integers. Integers can also represent strings of characters
  • Two types of radix sort are:
    • LSD (Least Significant Digit): Short keys come before long keys
    • MSD (Most Significant Digit) Sorting: Lexicographic Order. Better for strings.
  • Uses Counting Sort as Sub Routine (which takes extra memory)
    • If memory is not really a concern, forget about this issue
  • Radix Sort, with at most d digits, takes O(d*(n+b)) time where b is the base
  • Use Radix Sort over Counting Sort when the numbers range from 1 to n-square for example.

Numbers

Let’s look at the stats from the algorithm:

# of Items in Array Time Taken Average for 100 numbers
Random 10 0.033351 0.33351
1K 3.22004 0.322004
1M 5650.9 0.56509
Sorted 10 0.020659 0.20659
1K 3.26273 0.326273
1M 5683.91 0.568391

Code

As always, the code is available at https://github.com/abhi1010/Algorithms for easier access.

Advertisements

One thought on “Radix Sort

  1. Pingback: Heap Sort vs Merge Sort vs Insertion Sort vs Radix Sort vs Counting Sort vs Quick Sort |

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s