Sort is not a total order

[shelvacu]

Given this code:

#[test]
fn bunch_of_hexes() {
    let mut hexes = vec![
        "02", "75", "f7", "a0", "df", "ca", "5d", "08",
        "91", "b2", "e5", "47", "30", "8b", "6f", "1a",
        "b8", "82", "ee", "bb", "88", "11", "66", "29",
        "7e", "0b", "54", "23", "9a", "c1", "d6", "59",
        "0e", "7b", "24", "53", "9f", "d1", "85", "be",
        "eb", "61", "16", "e2", "b5", "37", "40", "8e",
        "1f", "6a", "72", "05", "f0", "cf", "da", "5c",
        "2d", "96", "78", "92", "a9", "cb", "de", "a3",
        "f4", "01", "98", "1b", "6e", "39", "8a", "33",
        "44", "e6", "b1", "65", "12", "ba", "ef", "81",
        "18", "4d", "3c", "d5", "c2", "9b", "20", "57",
        "0a", "7f", "ac", "c8", "c5", "d2", "9e", "27",
        "7a", "0f", "ad", "fc", "15", "62", "bf", "86",
        "3d", "4c", "6b", "1e", "49", "8f", "43", "34",
        "b6", "e1", "95", "db", "ce", "f3", "a4", "06",
        "71", "e9", "41", "36", "8d", "b4", "e3", "5b",
        "97", "79", "f1", "a6", "04", "73", "c7", "d0",
        "52", "25", "58", "7c", "af", "fa", "17", "60",
        "ec", "bd", "3f", "4a", "84", "89", "10", "bc",
        "ed", "4f", "3a", "83", "c0", "22", "55", "28",
        "0c", "7d", "ff", "aa", "5e", "2b", "09", "90",
        "a1", "f6", "74", "03", "b9", "31", "46", "8c",
        "e4", "b3", "e0", "b7", "35", "42", "1d", "6c",
        "48", "70", "07", "a5", "f2", "f8", "cd", "dc",
        "94", "5a", "2f", "fb", "d9", "9d", "26", "51",
        "d3", "c4", "69", "87", "4b",
    ];
    hexes.sort_by(|a, b| alphanumeric_sort::compare_str(a, b));
}

The test fails with user-provided comparison function does not correctly implement a total order

In case you're wondering where the list came from: This bug popped up for me when I was running dufs and tried to point some backup software at it. The resulting folders it created couldn't be sorted due to the mentioned error, and I extracted out a testcase from that. The list is 235 of the 256 hexadecimal numbers between 00 and ff, in the order that happened to be returned by the filesystem.

[shelvacu]

Much simpler repro:

#[test]
fn foo() {
    let a = "1a";
    let b = "01";
    assert_ne!(
        alphanumeric_sort::compare_str(a, b),
        alphanumeric_sort::compare_str(b, a),
    );
}