Repository: rust
Issue: Sorting a Slice Raises an Illegal Instruction Signal
Labels: C-bug,T-libs

As the issue title indicates, I have discovered that, in some cases, sorting a slice via `slice::sort` erroneously raises SIGILL (illegal instruction). Below is a minimal test case for the observed behavior.

```rust
use std::fmt;

#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
struct S(bool, [u8; 999_999]);

impl fmt::Debug for S {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Debug::fmt(&self.0, f)
    }
}

fn main() {
    let n = 101;
    let mut objs = Vec::with_capacity(n);

    let mut on = false;

    for _ in 0..n {
        objs.push(S(on, [0; 999_999]));
        on = !on;
    }

    println!("Done adding elements.");
    println!("Objects: {:?}", objs);

    objs.sort();

    println!("Objects: {:?}", objs);
}
```

If you run this code in a debugger, you will see that the SIGILL comes from the call to `core::intrinsics::abort` [here](https://github.com/rust-lang/rust/blob/f7cc13af822fe68c64fec0b05aa9dd1412451f7c/library/core/src/slice/sort/stable/quicksort.rs#L98). That is, something is causing `scratch.len()` to be less than `len` when it shouldn't be.

I think I have traced the cause of the problem to how `min_good_run_len` is calculated [here](https://github.com/rust-lang/rust/blob/f7cc13af822fe68c64fec0b05aa9dd1412451f7c/library/core/src/slice/sort/stable/drift.rs#L37). If `len <= MIN_SQRT_RUN_LEN * MIN_SQRT_RUN_LEN` holds true and `len - len / 2` (which is really just `ceil(len / 2)`) happens to be `<= MIN_SQRT_RUN_LEN`, then `min_good_run_len` is given the value `len - len / 2` (which, again, is just `ceil(len / 2)`). When the function `create_run` in the same file cannot find an ascending or descending run of at least `min_good_run_len` elements, it extracts an unsorted run that extends for `min_good_run_len` elements or until the end of the slice/array (whichever is earlier). Later, the function `logical_merge` in the same file will sort an unsorted run if it and the run with which it is to be merged do not together fit in `scratch`.

`scratch.len()` is at least `floor(len / 2)`, and `floor(len / 2)` is less than `ceil(len / 2)` when `len` is an odd integer, so a problem arises when `scratch.len()` is equal to `floor(len / 2)`, `min_good_run_len` is equal to `ceil(len / 2)`, and `len` is odd, because, then, `logical_merge` might try to sort an unsorted run that cannot fit in `scratch`. If my math is correct, this is exactly the situation occurring in my minimal test case.

Replacing `len - len / 2` with `len / 2` in the calculation of `min_good_run_len` would therefore fix the issue, if I am not mistaken. I do not know why the author(s) of the driftsort chose `len - len / 2` instead of `len / 2`. Neither the commit (in the original driftsort GitHub repository) where it first appeared (https://github.com/Voultapher/driftsort/commit/dbe1d246d9d35f4bafdbb2cbefb8d63e18fb7b52) nor the associated pull request (https://github.com/Voultapher/driftsort/pull/39) appears to give an explanation.

### Meta
`rustc --version --verbose`:
```
rustc 1.86.0-nightly (f7cc13af8 2025-01-25)
binary: rustc
commit-hash: f7cc13af822fe68c64fec0b05aa9dd1412451f7c
commit-date: 2025-01-25
host: x86_64-unknown-linux-gnu
release: 1.86.0-nightly
LLVM version: 19.1.7
```

<!-- TRIAGEBOT_START -->

<!-- TRIAGEBOT_ASSIGN_START -->

<!-- TRIAGEBOT_ASSIGN_DATA_START$${"user":"uellenberg"}$$TRIAGEBOT_ASSIGN_DATA_END -->

<!-- TRIAGEBOT_ASSIGN_END -->
<!-- TRIAGEBOT_END -->