Counting Sort

def counting_sort(items):
    """Stable counting sort for integer keys, including negatives."""
    if not items:
        return []

    low, high = min(items), max(items)
    k = high - low + 1
    count = [0] * k

    # 1. Frequencies. Offset maps [low, high] to [0, k).
    for value in items:
        count[value - low] += 1

    # 2. Prefix sums become exclusive right boundaries.
    for i in range(1, k):
        count[i] += count[i - 1]

    # 3. Right-to-left placement makes equal keys stable.
    output = [0] * len(items)
    for value in reversed(items):
        bucket = value - low
        count[bucket] -= 1
        output[count[bucket]] = value

    return output

class CountingSort {
    static int[] sort(int[] input) {
        if (input.length == 0) return new int[0];

        int min = input[0], max = input[0];
        for (int value : input) {
            min = Math.min(min, value);
            max = Math.max(max, value);
        }

        // Compute in long: max - min can overflow an int.
        long range = (long) max - min + 1;
        if (range > Integer.MAX_VALUE) {
            throw new IllegalArgumentException("Key range is too large");
        }

        int[] count = new int[(int) range];
        for (int value : input) count[value - min]++;
        for (int i = 1; i < count.length; i++) count[i] += count[i - 1];

        int[] output = new int[input.length];
        for (int i = input.length - 1; i >= 0; i--) {
            int bucket = input[i] - min;
            output[--count[bucket]] = input[i];
        }
        return output;
    }
}