# Radix Sort

Sep 13, 2012 · Commentscode 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.