Array original: [4, 2, 2, 8, 3, 3, 1]
Valores de 0 a 8 (k = 9)

Passo 1 — Contagem:
  Índice:   0  1  2  3  4  5  6  7  8
  Contagem: [0, 1, 2, 2, 1, 0, 0, 0, 1]
             ↑  ↑  ↑  ↑  ↑           ↑
             0× 1× 2× 2× 1×          1×

Passo 2 — Soma acumulada:
  Contagem: [0, 1, 3, 5, 6, 6, 6, 6, 7]
  Posição do último elemento de cada valor

Passo 3 — Posicionar (da direita para estabilidade):
  Original[6] = 1 → contagem[1]=1 → saída[0] = 1, contagem[1]=0
  Original[5] = 3 → contagem[3]=5 → saída[4] = 3, contagem[3]=4
  Original[4] = 3 → contagem[3]=4 → saída[3] = 3, contagem[3]=3
  ...

Resultado: [1, 2, 2, 3, 3, 4, 8] ✓

const std = @import("std");
const Allocator = std.mem.Allocator;

/// Counting Sort para inteiros não-negativos.
/// k é o valor máximo + 1 no array.
pub fn countingSort(
    allocator: Allocator,
    items: []u32,
    k: usize,
) !void {
    if (items.len <= 1) return;

    // Array de contagem
    const contagem = try allocator.alloc(usize, k);
    defer allocator.free(contagem);
    @memset(contagem, 0);

    // Array de saída
    const saida = try allocator.alloc(u32, items.len);
    defer allocator.free(saida);

    // Passo 1: contar ocorrências
    for (items) |valor| {
        contagem[valor] += 1;
    }

    // Passo 2: soma acumulada
    var i: usize = 1;
    while (i < k) : (i += 1) {
        contagem[i] += contagem[i - 1];
    }

    // Passo 3: posicionar (percorrendo de trás para frente = estável)
    var j: usize = items.len;
    while (j > 0) {
        j -= 1;
        const valor = items[j];
        contagem[valor] -= 1;
        saida[contagem[valor]] = valor;
    }

    // Copia de volta para o array original
    @memcpy(items, saida);
}

/// Counting Sort para inteiros com valores negativos.
/// Ajusta o intervalo para trabalhar com índices positivos.
pub fn countingSortComNegativos(
    allocator: Allocator,
    items: []i32,
) !void {
    if (items.len <= 1) return;

    // Encontra min e max
    var min_val: i32 = items[0];
    var max_val: i32 = items[0];
    for (items[1..]) |v| {
        if (v < min_val) min_val = v;
        if (v > max_val) max_val = v;
    }

    const intervalo: usize = @intCast(@as(i64, max_val) - @as(i64, min_val) + 1);

    const contagem = try allocator.alloc(usize, intervalo);
    defer allocator.free(contagem);
    @memset(contagem, 0);

    const saida = try allocator.alloc(i32, items.len);
    defer allocator.free(saida);

    // Conta ocorrências (ajustando pelo mínimo)
    for (items) |v| {
        const idx: usize = @intCast(@as(i64, v) - @as(i64, min_val));
        contagem[idx] += 1;
    }

    // Soma acumulada
    var i: usize = 1;
    while (i < intervalo) : (i += 1) {
        contagem[i] += contagem[i - 1];
    }

    // Posiciona (estável)
    var j: usize = items.len;
    while (j > 0) {
        j -= 1;
        const idx: usize = @intCast(@as(i64, items[j]) - @as(i64, min_val));
        contagem[idx] -= 1;
        saida[contagem[idx]] = items[j];
    }

    @memcpy(items, saida);
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    // Exemplo com inteiros não-negativos
    var numeros = [_]u32{ 4, 2, 2, 8, 3, 3, 1 };
    try stdout.print("Original:  ", .{});
    for (numeros) |n| try stdout.print("{d} ", .{n});
    try stdout.print("\n", .{});

    try countingSort(allocator, &numeros, 9);

    try stdout.print("Ordenado:  ", .{});
    for (numeros) |n| try stdout.print("{d} ", .{n});
    try stdout.print("\n", .{});

    // Exemplo com negativos
    var negativos = [_]i32{ -5, 3, -1, 0, 2, -3, 1 };
    try countingSortComNegativos(allocator, &negativos);

    try stdout.print("Negativos: ", .{});
    for (negativos) |n| try stdout.print("{d} ", .{n});
    try stdout.print("\n", .{});
}