Array original: [170, 45, 75, 90, 802, 24, 2, 66]

Passo 1 — Ordenar pelo dígito das unidades:
  170(0) 90(0) 802(2) 2(2) 24(4) 45(5) 75(5) 66(6)
  → [170, 90, 802, 2, 24, 45, 75, 66]

Passo 2 — Ordenar pelo dígito das dezenas:
  802(0) 2(0) 24(2) 45(4) 66(6) 170(7) 75(7) 90(9)
  → [802, 2, 24, 45, 66, 170, 75, 90]

Passo 3 — Ordenar pelo dígito das centenas:
  2(0) 24(0) 45(0) 66(0) 75(0) 90(0) 170(1) 802(8)
  → [2, 24, 45, 66, 75, 90, 170, 802] ✓

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

/// Radix Sort LSD (Least Significant Digit) para inteiros não-negativos.
pub fn radixSort(allocator: Allocator, items: []u32) !void {
    if (items.len <= 1) return;

    // Encontra o valor máximo para saber quantos dígitos processar
    var max_val: u32 = 0;
    for (items) |v| {
        if (v > max_val) max_val = v;
    }

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

    // Ordena por cada dígito, começando pelo menos significativo
    var exp: u64 = 1;
    while (max_val / @as(u32, @intCast(exp)) > 0) : (exp *= 10) {
        countingSortPorDigito(items, saida, @intCast(exp));
    }
}

/// Counting Sort estável para um dígito específico.
fn countingSortPorDigito(items: []u32, saida: []u32, exp: u32) void {
    var contagem = [_]usize{0} ** 10; // dígitos 0-9

    // Conta ocorrências do dígito
    for (items) |v| {
        const digito = (v / exp) % 10;
        contagem[digito] += 1;
    }

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

    // Posiciona (de trás para frente = estável)
    var j: usize = items.len;
    while (j > 0) {
        j -= 1;
        const digito = (items[j] / exp) % 10;
        contagem[digito] -= 1;
        saida[contagem[digito]] = items[j];
    }

    // Copia de volta
    @memcpy(items, saida);
}

/// Radix Sort em base 256 (por bytes) — mais eficiente para u32.
/// Processa 4 bytes em vez de ~10 dígitos decimais.
pub fn radixSort256(allocator: Allocator, items: []u32) !void {
    if (items.len <= 1) return;

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

    // Processa cada byte (4 passagens para u32)
    comptime var byte_idx: u5 = 0;
    inline while (byte_idx < 4) : (byte_idx += 1) {
        const shift: u5 = byte_idx * 8;
        var contagem = [_]usize{0} ** 256;

        // Conta
        for (items) |v| {
            const byte_val = @as(u8, @truncate(v >> shift));
            contagem[byte_val] += 1;
        }

        // Acumula
        var i: usize = 1;
        while (i < 256) : (i += 1) {
            contagem[i] += contagem[i - 1];
        }

        // Posiciona
        var j: usize = items.len;
        while (j > 0) {
            j -= 1;
            const byte_val = @as(u8, @truncate(items[j] >> shift));
            contagem[byte_val] -= 1;
            saida[contagem[byte_val]] = 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();

    var numeros = [_]u32{ 170, 45, 75, 90, 802, 24, 2, 66 };

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

    try radixSort(allocator, &numeros);

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

    // Versão base 256
    var nums2 = [_]u32{ 1000000, 500, 123456, 789, 42 };
    try radixSort256(allocator, &nums2);

    try stdout.print("Base 256:  ", .{});
    for (nums2) |n| try stdout.print("{d} ", .{n});
    try stdout.print("\n", .{});
}