Counting Sort in Python, Java and TypeScript

Counting sort with an offset for the smallest value, printing the counts, the end positions and the output.

A counting sort is three loops: one to count, one to turn the counts into end positions, and one to place the items. The listings below sort 13 4 10 7 14 3 10, subtract the smallest key so the count array starts at it rather than at zero, print the counts and the end positions, and check the result against the built-in sort.

Counting sort with an offset for the smallest key, in each language

counting_code.pypy

def counting_sort(items: list[int]) -> list[int]:
    low = min(items)
    counts = [0] * (max(items) - low + 1)
    print(f"low: {low}, k: {len(counts)}")
    for value in items:
        counts[value - low] += 1
    print("counts:", show(counts))
    for index in range(1, len(counts)):
        counts[index] += counts[index - 1]
    print("ends:", show(counts))
    output = [0] * len(items)
    for value in reversed(items):
        counts[value - low] -= 1
        output[counts[value - low]] = 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(counting_sort(numbers)))
print("built-in:", show(sorted(numbers)))

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

low: 3, k: 12
counts: 1 1 0 0 1 0 0 2 0 0 1 1
ends: 1 2 2 2 3 3 3 5 5 5 6 7
sorted: 3 4 7 10 10 13 14
built-in: 3 4 7 10 10 13 14

CountingCode.javajava

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

public class CountingCode {
    static int[] countingSort(int[] items) {
        int low = Arrays.stream(items).min().getAsInt();
        int[] counts = new int[Arrays.stream(items).max().getAsInt() - low + 1];
        System.out.println("low: " + low + ", k: " + counts.length);
        for (int value : items) {
            counts[value - low]++;
        }
        System.out.println("counts: " + show(counts));
        for (int index = 1; index < counts.length; index++) {
            counts[index] += counts[index - 1];
        }
        System.out.println("ends: " + show(counts));
        int[] output = new int[items.length];
        for (int i = items.length - 1; i >= 0; i--) {
            counts[items[i] - low]--;
            output[counts[items[i] - low]] = 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(countingSort(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)

low: 3, k: 12
counts: 1 1 0 0 1 0 0 2 0 0 1 1
ends: 1 2 2 2 3 3 3 5 5 5 6 7
sorted: 3 4 7 10 10 13 14
built-in: 3 4 7 10 10 13 14

counting_code.tsts

function countingSort(items: number[]): number[] {
  const low = Math.min(...items);
  const counts = new Array<number>(Math.max(...items) - low + 1).fill(0);
  console.log(`low: ${low}, k: ${counts.length}`);
  for (const value of items) {
    counts[value - low]++;
  }
  console.log(`counts: ${counts.join(" ")}`);
  for (let index = 1; index < counts.length; index++) {
    counts[index] += counts[index - 1];
  }
  console.log(`ends: ${counts.join(" ")}`);
  const output = new Array<number>(items.length).fill(0);
  for (let i = items.length - 1; i >= 0; i--) {
    counts[items[i] - low]--;
    output[counts[items[i] - low]] = items[i];
  }
  return output;
}

const numbers = [13, 4, 10, 7, 14, 3, 10];
console.log(`sorted: ${countingSort(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

low: 3, k: 12
counts: 1 1 0 0 1 0 0 2 0 0 1 1
ends: 1 2 2 2 3 3 3 5 5 5 6 7
sorted: 3 4 7 10 10 13 14
built-in: 3 4 7 10 10 13 14

All three printed the same lines. The smallest key is 3, so the count array has k = 14 − 3 + 1 = 12 cells, where the version on the Counting Sort card, which started at zero, had 15. Cell 0 counts the 3s and cell 7 counts the 10s, which is why it holds 2.

The highlighted lines are the placing loop. It walks the input from the last item, takes one from the item's cell, and writes the item at the index that leaves, which keeps equal keys in their input order. Every access to the count array subtracts low, so the sort works for negative keys too: temperatures from −40 to 60 fit in 101 cells, where an array starting at zero would have no cell for −40 at all.

In real code, use the built-in sort unless profiling shows the sort matters and the keys fit. None of the three languages' built-in sorts is a counting sort, because a library sort cannot know the range of the keys it will be given. When the keys are small integers and the input is large, a hand-written counting sort like this one is the standard optimisation.

← → move through sections and cards