tiny.simd.countingSort

1pub fn countingSort(2    comptime T: type,3    values: []T,4    scratch: []CountingSortEntry(T),5) Error!void {6    comptime requireInteger(T);7    const Entry = CountingSortEntry(T);8    var unique_count: usize = 0;9    for (values) |value| {10        var unique_index: usize = 0;11        while (unique_index < unique_count and scratch[unique_index].value != value) {12            unique_index += 1;13        }14        if (unique_index == unique_count) {15            if (unique_count == scratch.len) return error.InsufficientScratch;16            scratch[unique_count] = .{ .value = value, .count = 1 };17            unique_count += 1;18        } else {19            scratch[unique_index].count += 1;20        }21    }2223    std.mem.sort(Entry, scratch[0..unique_count], {}, EntryAscending(Entry).lessThan);2425    var output_index: usize = 0;26    for (scratch[0..unique_count]) |entry| {27        const end = output_index + entry.count;28        @memset(values[output_index..end], entry.value);29        output_index = end;30    }31    std.debug.assert(output_index == values.len);32}

1pub const countingSort = robust.countingSort;