Radix Sort in Python, Java and TypeScript

LSD radix sort in base 10, using a counting pass per digit and printing the array after each pass.

An LSD radix sort is a loop over digit positions around a counting pass whose key is one digit. The listings below sort 13 4 10 7 14 3 10 in base 10, print the array after the pass on each digit, and check the result against the built-in sort. The loop stops once the place value is larger than the largest key, so the number of passes is the number of digits in that key.

LSD radix sort with a stable counting pass per decimal digit, in each language

radix_code.pypy

def radix_sort(items: list[int]) -> list[int]:
    place = 1
    while max(items) // place > 0:
        items = counting_pass(items, place)
        print(f"by digit {place}:", show(items))
        place *= 10
    return items


def counting_pass(items: list[int], place: int) -> list[int]:
    counts = [0] * 10
    for value in items:
        counts[value // place % 10] += 1
    for digit in range(1, 10):
        counts[digit] += counts[digit - 1]
    output = [0] * len(items)
    for value in reversed(items):
        counts[value // place % 10] -= 1
        output[counts[value // place % 10]] = value
    return output


def show(values: list[int]) -> str:
    return " ".join(map(str, values))


numbers = [13, 4, 10, 7, 14, 3, 10]
print("sorted:", show(radix_sort(numbers)))
print("built-in:", show(sorted(numbers)))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

by digit 1: 10 10 13 3 4 14 7
by digit 10: 3 4 7 10 10 13 14
sorted: 3 4 7 10 10 13 14
built-in: 3 4 7 10 10 13 14

RadixCode.javajava

import java.util.Arrays;
import java.util.stream.Collectors;

public class RadixCode {
    static int[] radixSort(int[] items) {
        int largest = Arrays.stream(items).max().getAsInt();
        for (int place = 1; largest / place > 0; place *= 10) {
            items = countingPass(items, place);
            System.out.println("by digit " + place + ": " + show(items));
        }
        return items;
    }

    static int[] countingPass(int[] items, int place) {
        int[] counts = new int[10];
        for (int value : items) {
            counts[value / place % 10]++;
        }
        for (int digit = 1; digit < 10; digit++) {
            counts[digit] += counts[digit - 1];
        }
        int[] output = new int[items.length];
        for (int i = items.length - 1; i >= 0; i--) {
            counts[items[i] / place % 10]--;
            output[counts[items[i] / place % 10]] = items[i];
        }
        return output;
    }

    static String show(int[] values) {
        return Arrays.stream(values).mapToObj(String::valueOf).collect(Collectors.joining(" "));
    }

    public static void main(String[] args) {
        int[] numbers = {13, 4, 10, 7, 14, 3, 10};
        System.out.println("sorted: " + show(radixSort(numbers)));
        int[] copy = numbers.clone();
        Arrays.sort(copy);
        System.out.println("built-in: " + show(copy));
    }
}

OutputRan with eclipse-temurin:25.0.4.1_1-jdk-noble (Java 25.0.4.1)

by digit 1: 10 10 13 3 4 14 7
by digit 10: 3 4 7 10 10 13 14
sorted: 3 4 7 10 10 13 14
built-in: 3 4 7 10 10 13 14

radix_code.tsts

function radixSort(items: number[]): number[] {
  const largest = Math.max(...items);
  for (let place = 1; Math.floor(largest / place) > 0; place *= 10) {
    items = countingPass(items, place);
    console.log(`by digit ${place}: ${items.join(" ")}`);
  }
  return items;
}

function countingPass(items: number[], place: number): number[] {
  const digitOf = (value: number): number => Math.floor(value / place) % 10;
  const counts = new Array<number>(10).fill(0);
  for (const value of items) {
    counts[digitOf(value)]++;
  }
  for (let digit = 1; digit < 10; digit++) {
    counts[digit] += counts[digit - 1];
  }
  const output = new Array<number>(items.length).fill(0);
  for (let i = items.length - 1; i >= 0; i--) {
    counts[digitOf(items[i])]--;
    output[counts[digitOf(items[i])]] = items[i];
  }
  return output;
}

const numbers = [13, 4, 10, 7, 14, 3, 10];
console.log(`sorted: ${radixSort(numbers).join(" ")}`);
console.log(`built-in: ${[...numbers].sort((a, b) => a - b).join(" ")}`);

OutputRan with node:24.22.0-trixie-slim (Node 24.22.0), TypeScript 5.9.3

by digit 1: 10 10 13 3 4 14 7
by digit 10: 3 4 7 10 10 13 14
sorted: 3 4 7 10 10 13 14
built-in: 3 4 7 10 10 13 14

All three printed the same two passes as the trace on the Radix Sort card: 10 10 13 3 4 14 7 after the ones digit, then the sorted array after the tens digit.

The highlighted lines read the digit. Dividing by the place value, 1 or 10, drops the digits to its right, and taking the remainder after dividing by 10 drops the digits to its left, so 13 // 10 % 10 is 1 and 13 // 1 % 10 is 3. TypeScript names the expression once as digitOf, because its division gives a fraction and needs Math.floor. The rest of the counting pass is the counting sort from Counting Sort in Python, Java and TypeScript with the digit in place of the key, and it keeps that listing's backwards placing loop, which is what keeps every pass stable.

The listing handles non-negative integers. Negative keys need either an offset that makes every key non-negative or a final pass that moves the negative keys in front, in reverse. Production radix sorts usually work in base 256 or 65,536 and read digits with shifts and masks, value >> shift & 0xFF, which is cheaper than division.

← → move through sections and cards