Input of 129 `u32`values which is not sorted correctly by rdst

[jix]

I noticed that rdst wouldn't reliably sort inputs and managed to reduce it down from my 80 GB of [u8; 36] input use case down to this small testcase, which fails consistently for me:

#[test]
fn broken_radix_sort() {
    let input: [u32; 129] = [
        0x10001, 0x1010000, 0, 0, 0x10000, 0x1000000, 0x1000000, 0x1010000, 0x1010000, 0,
        0x1000000, 0, 0x10000, 0, 0x1000000, 0x1010000, 0x1010000, 0x1010000, 0, 0, 0, 0,
        0x1000000, 0x1010000, 0x1000000, 0x10000, 0, 0x10000, 0x1000000, 0x1000000, 0x1010000,
        0x10000, 0x10000, 0x1000000, 0x1000000, 0, 0x10000, 0x1010000, 0x1000000, 0, 0x10000,
        0x1010000, 0x1000000, 0x1000000, 0x1000000, 0, 0x1010000, 0x1010000, 0, 0x1000000, 0x10000,
        0x1010000, 0x10000, 0, 0x10000, 0x1000000, 0x1010000, 0x1000000, 0x1010000, 0x10000,
        0x10000, 0x10000, 0x1000000, 0x10000, 0x1010000, 0x1000000, 0x1010000, 0x10000, 0,
        0x1000000, 0x1010000, 0x10000, 0, 0x1010000, 0x1010000, 0x10000, 0x10000, 0x1010000,
        0x1010000, 0x10000, 0, 0x10000, 0x10000, 0x10000, 0x10000, 0, 0x1000000, 0x10000,
        0x1000000, 0x1010000, 0x1010000, 0x10000, 0, 0x1010000, 0x1010000, 0x1010000, 0x10000,
        0x1000000, 0x1010000, 0x10000, 0x1000000, 0x1010000, 0x1010000, 0, 0x1000000, 0x1010000,
        0x10000, 0x1000000, 0x1010000, 0x1000000, 0, 0x1000000, 0x1010000, 0x1010000, 0x10000,
        0x1010000, 0, 0, 0x1010000, 0x1010000, 0, 0, 0x1010000, 0x1010000, 0, 0x1000000, 0x1000000,
        0x1000000, 0,
    ];

    let mut sort_with_radix = input;
    let mut sort_with_std = input;

    sort_with_radix.radix_sort_unstable();
    sort_with_std.sort_unstable();

    assert_eq!(sort_with_radix, sort_with_std);
}

thread 'broken_radix_sort' panicked at 'assertion failed: `(left == right)`
  left: `[0, 0, 65536, 0, 0, 65536, 0, 0, 0, 0, 0, 65536, 0, 65536, 65536, 65536, 0, 65536, 0, 65536, 0, 0, 65536, 65536, 0, 65536, 65536, 65536, 65536, 65536, 65536, 0, 65536, 0, 65536, 65536, 65536, 0, 65536, 65536, 65536, 65536, 0, 65536, 65536, 0, 65536, 65536, 0, 65536, 0, 65536, 0, 0, 0, 0, 0, 0, 65537, 16842752, 16777216, 16777216, 16842752, 16842752, 16777216, 16777216, 16842752, 16842752, 16842752, 16777216, 16842752, 16777216, 16777216, 16777216, 16842752, 16777216, 16777216, 16842752, 16777216, 16842752, 16777216, 16777216, 16777216, 16842752, 16842752, 16777216, 16842752, 16777216, 16842752, 16777216, 16842752, 16777216, 16842752, 16777216, 16842752, 16777216, 16842752, 16842752, 16842752, 16842752, 16842752, 16777216, 16777216, 16842752, 16842752, 16842752, 16842752, 16842752, 16777216, 16842752, 16777216, 16842752, 16842752, 16777216, 16842752, 16777216, 16842752, 16777216, 16777216, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16777216, 16777216, 16777216]`,
 right: `[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65536, 65537, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16777216, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752, 16842752]`', src/main.rs:233:5

[nessex]

Thanks for the report, and replication case!

This happened when there was an n'th byte that for all inputs was zero, with non-zero bytes afterwards. This would inadvertently re-use the byte counts for the previous byte (zero) for all following bytes.

I've fixed this in 0.20.11 along with a couple of other edge cases. You can see the changes here: https://github.com/Nessex/rdst/commit/f5ad4536741a49ad961cb543e030847d7ebf6ce3