Skip to content

Radix Sort

April 6, 2013

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.

Advertisements

From → Algorithms

Leave a Comment

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: