Radix Sort Algorithm

5 min readSep 25, 2022

A non in-place sorting algorithm that sorts numbers digit by digit based on individual digit position. We can sort starting from the least significant digit(LSD) to the most significant digit(MSD) or vice versa. Radix sort can incorporate different sorting algorithms to sort digits of the same place value. In this article, we implement LSD radix sort using counting sort as subroutine to sort and MSD radix sort recursively performing bucket sort to sort. Radix sort runs in O(d*(n+b)) time. (d: the max number of digits, n: the length of the array to be sorted, b: the numbering system used)

Table of Contents· How Does Radix Sort Algorithm Work?
  ∘ LSD Radix Sort
  ∘ MSD Radix Sort
· Graphical Explanation
  ∘ Positive array
  ∘ Array contains negative values
· Code Implementation
  ∘ Complexity
  ∘ Pseudocode
  ∘ Golang
  ∘ Python

How Does Radix Sort Algorithm Work?

Radix sort algorithm sorts numbers by digits in a particular place value. There are two types of radix sort according to the sorting order.

LSD Radix Sort

LSD radix sort starts the sorting from the least significant digit and employs a stable sorting algorithm as a subroutine to sort digits of the same place value. It touches all of the digits to get the sorted array.

MSD Radix Sort

MSD radix sort starts the sorting from the most significant digit. It assigns digits of the same place value to different buckets and then recursively sorts each bucket until every bucket has one or no element left.

MSD radix may not need to examine every single digit of each number to get a sorted output, so it is considerably faster than LSD radix sort. However, it requires more space than LSD radix sort because of recursive implementation.

Graphical Explanation

There are many ways to implement radix sort. We use counting sort as subroutine to sort for LSD radix sort and recursively perform bucket sort in MSD radix sort for demo.

Positive array

LSD Radix Sort
- step1: get the maximum value in the array
- step2: start sorting from the least significant digit to the most significant digit using counting sort as subroutine

If you are not familiar with counting sort, please check here for details.

floor(maxValue/placeValue) > 0 => still have digits to be sorted
floor(maxValue/placeValue) < 0 => stop sorting

MSD Radix Sort
- step1: get the maximum value in the array (for calculating the leftmost place value)
- step2: start sorting from the most significant digit to the least significant digit

Recursively implement bucket sort to sort each digit group

If you are not familiar with bucket sort, please check here for details.

Array contains negative values

use offset to deal with negative values

LSD Radix Sort
- step1: get the maximum value in the array
- step2: start sorting from the least significant digit to the most significant digit using counting sort as subroutine

floor(maxValue/placeValue) > 0 => still have digits to be sorted
floor(maxValue/placeValue) < 0 => stop sorting

MSD Radix Sort
- step1: get the maximum value in the array (for calculating the leftmost place value)
- step2: start sorting from the most significant digit to the least significant digit

Recursively implement bucket sort to sort each digit group

Code Implementation

Complexity

Time: O(d*(n+b))
Space: O(n+b)
n: the total number of elements in the input array
d: the max number of digits
b: the base of the numbering system used

Pseudocode

LSD Radix Sort

# the base of the numbering system used
base# get the maximum element in the array
maxValue = max(array)# sort from the least significant digit
placeValue = 1
while floor(maxValue / placeValue) > 0:
    # use counting sort as a subroutine
    countingSort(array, placeValue)
    placeValue *= base

MSD Radix Sort

# the base of the numbering system used
base# get the maximum element in the array
maxValue = max(array)
numberOfDigits = getNumberOfDigits(maxValue)# sort from the most significant digit
placeValue = base**(numberOfDigits-1)# recursive function
bucketSort(array, placeValue)

Golang

offset is used to handle negative values

LSD Radix Sort

MSD Radix Sort

Python