# Radix Sort

Radix sort is a non-comparison based sorting algorithm, which is then not bound by the O(N log N) lower bound proven for comparison based sort algorithm. Radix sort is a linear time sorting algorithm O(kN), where k is the key length. There are 2 popular approaches to Radix sorting: LSD (Least Significant Digit) and MSD (Most Significant Digit).

3-way Radix Quicksort was invented in 1999 by Bentley and Sedgewick.

An interesting video of then Google CEO, Eric Schmidt, asking then Senator Obama an interview question and the best answer is Radix sort. Since the maximum number of base 10 digits for a 32-bit integer would be: 10 digits 2^32 = 4,294,967,296. Since Radix Sort would make D passes over the N=1,000,000 numbers, it would be at most 10*N compares. A comparison sort like mergesort would require (N lg N) = log2(1,000,000)=almost 20, and therefore would take at least 20*N compares.