Skip to content

LSD radix sort

Problem

Implement least-significant-digit radix sort for signed integers.

Key trick

Apply a stable counting-sort pass to one digit at a time, from least significant to most significant.

The complexity is \(O(d(n+b))\), where \(d\) is the number of digits and \(b\) is the base.

Linked-list radix sort can use linked bucket queues, but merge sort is usually simpler and more general.

Trap

Every digit pass must be stable; signed values also require explicit handling.

Why is it interesting?

It sorts fixed-width integer-like keys without comparing entire values.

Python solution

class sort_radix_sort:
    def sort(self, nums: list[int]) -> list[int]:
        # Sort absolute negative values separately because the digit routine
        # only handles nonnegative integers.
        negatives = [-x for x in nums if x < 0]
        nonnegatives = [x for x in nums if x >= 0]

        sorted_negatives = self._radix_nonnegative(negatives)
        sorted_nonnegatives = self._radix_nonnegative(nonnegatives)

        # Larger absolute values represent smaller negative numbers.
        # Reverse their order before restoring the negative sign.
        return (
            [-x for x in reversed(sorted_negatives)]
            + sorted_nonnegatives
        )

    def _radix_nonnegative(
        self,
        nums: list[int],
        base: int = 10,
    ) -> list[int]:
        arr = nums[:]

        if not arr:
            return arr

        max_val = max(arr)

        # `exp` selects the current digit:
        # 1 for units, 10 for tens, 100 for hundreds, and so on.
        exp = 1

        while max_val // exp > 0:
            counts = [0] * base
            res = [0] * len(arr)

            # Count values by the current digit.
            for x in arr:
                digit = x // exp % base
                counts[digit] += 1

            # Convert frequencies into cumulative ending positions.
            for digit in range(1, base):
                counts[digit] += counts[digit - 1]

            # A stable digit pass is essential to radix sort.
            # Right-to-left traversal preserves prior digit ordering.
            for x in reversed(arr):
                digit = x // exp % base
                counts[digit] -= 1
                res[counts[digit]] = x

            arr = res

            # Move to the next more significant digit.
            exp *= base

        return arr