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
• r = radix

The radix

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) {
            CountingSortByDigit(array, radix, exponent, minValue);
            exponent *= radix;
        }
    }

    public void CountingSortByDigit(
            int[] array, int radix, int exponent, int minValue) {
        int bucketIndex;
        int[] buckets = new int[radix];
        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) {
        RadixSort.sort(array, 10);
    }

    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) {
            RadixSort.countingSortByDigit(array, radix, exponent, minValue);
            exponent *= radix;
        }
    }

    private static void countingSortByDigit(
            Integer[] array, int radix, int exponent, int minValue) {
        int bucketIndex;
        int[] buckets = new int[radix];
        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.
 * @param {number} [radix=10] The base/radix to use.
 * @returns The sorted array.
 */
function sort(array, radix) {
  if (array.length === 0) {
    return array;
  }

  radix = radix || 10;

  // 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);

    exponent *= radix;
  }

  return array;
}

/**
 * Stable sorts an array by a particular digit using counting sort.
 * @param {Array} array The array to sort.
 * @param {number} radix The base/radix to use 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 buckets = new Array(radix);
  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)
    exponent *= radix

  return array

def countingSortByDigit(array, radix, exponent, minValue):
  bucketIndex = -1
  buckets = [0] * radix
  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
  for i in range(1, radix):
    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.
  def self.sort(array, radix = 10)
    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
      countingSortByDigit(array, radix, exponent, minValue)
      exponent *= radix
    end
  end

private

  # Stable sorts an array by a particular digit using counting sort.
  def self.countingSortByDigit(array, radix, exponent, minValue)
    buckets = Array.new(radix)
    output = Array.new(array.length)

    # Initialize bucket
    (0..radix - 1).each do |i|
      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
    (1..radix - 1).each do |i|
      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.

 

More posts tagged Sorting