# Growing with the Web

Published
Tags:

LSD radix sort is a stable distribution sort similar to bucket sort, that distributes values into buckets based on the digits within the value.

The LSD variant of radix sort performs a stable counting sort on the list for each digit, starting from the least significant (right-most) digit. It runs in O(wn) time where n is the input size and w is the word size (the number of digits in the largest number for the given radix).

LSD radix sort is stable, unlike the MSD variant as the relative order is retained after each sorting iteration.

## Complexity

Time Space
Worst case Best case Average case Worst case
O(wn) O(wn) O(wn) O(n + r) auxiliary

Where:

• n = input size
• w = word size

The algorithm is named radix sort as it specifies the radix r to be used which changes how the sort is performed. The radix, or base, of the number system is the number of digits that represent a single position in the number; a radix of 2 is binary (0-1), 10 is decimal (0-9), 16 is hexadecimal (0-F) and so on. Since the radix determines the number of buckets in addition to the word size w used in the algorithm, changing it can drastically change how the sort plays out:

## When it’s fast

Since comparison sorts cannot perform better than O(n\log n), LSD radix sort is considered one of the best alternatives provided the word size w is expected to be less than \log n.

It does however have limitations on the type of keys that can be sorted in that they need to have some way of being split up (ie. the radix), so it’s typically only used for string (where r=255 for ASCII characters) and integer keys.

## When it’s slow

Radix sort is slowest when the word size is large, such as when there is a large key range but small radix. The reason that a large radix is not always used is because then it essentially becomes counting sort, with the large memory footprint associated with it.

## Code

public class RadixSort : IIntegerSortingAlgorithm {
public void Sort(int[] array) {
Sort(array, 10);
}

public void Sort(int[] array, int radix) {
if (array.Length == 0) {
return;
}

// Determine minimum and maximum values
int minValue = array[0];
int maxValue = array[0];
for (int i = 1; i < array.Length; i++) {
if (array[i] < minValue) {
minValue = array[i];
} else if (array[i] > maxValue) {
maxValue = array[i];
}
}

// Perform counting sort on each exponent/digit, starting at the least
// significant digit
int exponent = 1;
while ((maxValue - minValue) / exponent >= 1) {
}
}

public void CountingSortByDigit(
int[] array, int radix, int exponent, int minValue) {
int bucketIndex;
int[] output = new int[array.Length];

// Initialize bucket
for (int i = 0; i < radix; i++) {
buckets[i] = 0;
}

// Count frequencies
for (int i = 0; i < array.Length; i++) {
bucketIndex = (int)(((array[i] - minValue) / exponent) % radix);
buckets[bucketIndex]++;
}

// Compute cumulates
for (int i = 1; i < radix; i++) {
buckets[i] += buckets[i - 1];
}

// Move records
for (int i = array.Length - 1; i >= 0; i--) {
bucketIndex = (int)(((array[i] - minValue) / exponent) % radix);
output[--buckets[bucketIndex]] = array[i];
}

// Copy back
for (int i = 0; i < array.Length; i++) {
array[i] = output[i];
}
}
}
public class RadixSort {
public static void sort(Integer[] array) {
}

public static void sort(Integer[] array, int radix) {
if (array.length == 0) {
return;
}

// Determine minimum and maximum values
int minValue = array[0];
int maxValue = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] < minValue) {
minValue = array[i];
} else if (array[i] > maxValue) {
maxValue = array[i];
}
}

// Perform counting sort on each exponent/digit, starting at the least
// significant digit
int exponent = 1;
while ((maxValue - minValue) / exponent >= 1) {
}
}

private static void countingSortByDigit(
Integer[] array, int radix, int exponent, int minValue) {
int bucketIndex;
int[] output = new int[array.length];

// Initialize bucket
for (int i = 0; i < radix; i++) {
buckets[i] = 0;
}

// Count frequencies
for (int i = 0; i < array.length; i++) {
bucketIndex = (int)(((array[i] - minValue) / exponent) % radix);
buckets[bucketIndex]++;
}

// Compute cumulates
for (int i = 1; i < radix; i++) {
buckets[i] += buckets[i - 1];
}

// Move records
for (int i = array.length - 1; i >= 0; i--) {
bucketIndex = (int)(((array[i] - minValue) / exponent) % radix);
output[--buckets[bucketIndex]] = array[i];
}

// Copy back
for (int i = 0; i < array.length; i++) {
array[i] = output[i];
}
}
}
/**
* Sorts an array using radix sort.
* @param {Array} array The array to sort.
* @returns The sorted array.
*/
if (array.length === 0) {
return array;
}

// Determine minimum and maximum values
var minValue = array[0];
var maxValue = array[0];
for (var i = 1; i < array.length; i++) {
if (array[i] < minValue) {
minValue = array[i];
} else if (array[i] > maxValue) {
maxValue = array[i];
}
}

// Perform counting sort on each exponent/digit, starting at the least
// significant digit
var exponent = 1;
while ((maxValue - minValue) / exponent >= 1) {
array = countingSortByDigit(array, radix, exponent, minValue);

}

return array;
}

/**
* Stable sorts an array by a particular digit using counting sort.
* @param {Array} array The array to sort.
* @param {number} exponent The exponent of the significant digit to sort.
* @param {number} minValue The minimum value within the array.
* @returns The sorted array.
*/
function countingSortByDigit(array, radix, exponent, minValue) {
var i;
var bucketIndex;
var output = new Array(array.length);

// Initialize bucket
for (i = 0; i < radix; i++) {
buckets[i] = 0;
}

// Count frequencies
for (i = 0; i < array.length; i++) {
bucketIndex = Math.floor(((array[i] - minValue) / exponent) % radix);
buckets[bucketIndex]++;
}

// Compute cumulates
for (i = 1; i < radix; i++) {
buckets[i] += buckets[i - 1];
}

// Move records
for (i = array.length - 1; i >= 0; i--) {
bucketIndex = Math.floor(((array[i] - minValue) / exponent) % radix);
output[--buckets[bucketIndex]] = array[i];
}

// Copy back
for (i = 0; i < array.length; i++) {
array[i] = output[i];
}

return array;
}
def sort(array, radix=10):
if len(array) == 0:
return array

# Determine minimum and maximum values
minValue = array[0];
maxValue = array[0];
for i in range(1, len(array)):
if array[i] < minValue:
minValue = array[i]
elif array[i] > maxValue:
maxValue = array[i]

# Perform counting sort on each exponent/digit, starting at the least
# significant digit
exponent = 1
while (maxValue - minValue) / exponent >= 1:
array = countingSortByDigit(array, radix, exponent, minValue)

return array

bucketIndex = -1
output = [None] * len(array)

# Count frequencies
for i in range(0, len(array)):
bucketIndex = math.floor(((array[i] - minValue) / exponent) % radix)
buckets[bucketIndex] += 1

# Compute cumulates
buckets[i] += buckets[i - 1]

# Move records
for i in range(len(array) - 1, -1, -1):
bucketIndex = math.floor(((array[i] - minValue) / exponent) % radix)
buckets[bucketIndex] -= 1
output[buckets[bucketIndex]] = array[i]

return output
module RadixSort
# Sorts an array using radix sort.
if array.length <= 1
return array
end

# Determine minimum and maximum values
minValue = array[0]
maxValue = array[0]
(1..array.length - 1).each do |i|
if array[i] < minValue
minValue = array[i]
elsif array[i] > maxValue
maxValue = array[i]
end
end

# Perform counting sort on each exponent/digit, starting at the least
# significant digit
exponent = 1
while (maxValue - minValue) / exponent >= 1
end
end

private

# Stable sorts an array by a particular digit using counting sort.
output = Array.new(array.length)

# Initialize bucket
buckets[i] = 0
end

# Count frequencies
(0..array.length - 1).each do |i|
bucketIndex = (((array[i] - minValue) / exponent) % radix).floor
buckets[bucketIndex] += 1
end

# Compute cumulates
buckets[i] += buckets[i - 1]
end

# Move records
(array.length - 1).downto(0) do |i|
bucketIndex = (((array[i] - minValue) / exponent) % radix).floor
buckets[bucketIndex] -= 1
output[buckets[bucketIndex]] = array[i]
end

# Copy back
(0..array.length - 1).each do |i|
array[i] = output[i]
end
end
end

## References

• R. Sedgewick, K. Wayne, “Strings” in Algorithms, 4nd ed., Boston, MA: Addison-Wesley, 2011, ch. 5, sec. 5.1, p.706-709

## Textbooks

Here are two CS textbooks I personally recommend; the Algorithm Design Manual (Steven S. Skiena) is a fantastic introduction to data structures and algorithms without getting to deep into the maths side of things, and Introduction to Algorithms (CLRS) which provides a much deeper, math heavy look.