Radix Sort Implementations

Radix Sort is a high performance linear time sorting algorithm, which does not use comparisons. Instead, Radix Sort looks at each digit of the key and processes based on those digits.

Two variations of the algorithm exit: least significant digit (LSD), and most significant digit (MSD). Each of the two variations has its own attributes, benefits and drawbacks. Performance comparison for sorting arrays of random unsigned 32-bit integers can be seen in one of my previous posts C++ Sorting Algorithms. LSD Radix Sort is faster than MSD Radix Sort for those implementations when sorting arrays of 32-bit unsigned random integers.

MSD Radix Sort

MSD Radix Sort processes each array element starting with the most significant digit as is explained in Radix Sort (MSD) Algorithm Core Concepts. MSD Radix Sort can be in-place as shown in In-place Hybrid Binary-Radix Sort, where sorting is done 1-bit at a time. Performance is improved sorting N-bits at a time In-place Hybrid N-bit-Radix Sort. Stable MSD Radix Sort can be implemented Stable Hybrid MSD N-bit-Radix Sort, giving up the ability to be in-place, but gaining performance.

Open question: Can MSD Radix Sort be in-place and stable?

Open question: Are stability and in-place mutually exclusive?

LSD Radix Sort

LSD Radix Sort is stable, but not in-place Faster Sorting in JavaScript. This implementation was ported from my C++ implementation, which I have not previously published.

Open question: Can LSD Radix Sort be made in-place?

 

 

Advertisements

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