Radix Sort

Sep 13, 2012 · Comments
code sortingalgoc++

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.