Tracking issue for release notes of #124032: Replace sort implementations

[rustbot]

This issue tracks the release notes text for #124032.

• Issue is nominated for the responsible team (and T-release nomination is removed).
• Proposed text is drafted by team responsible for underlying change.
• Issue is nominated for release team review of clarity for wider audience.
• Release team includes text in release notes/blog posts.

Release notes text:

The section title will be de-duplicated by the release team with other release notes issues.
Prefer to use the standard titles from previous releases.
More than one section can be included if needed.

# Compatibility Notes
- [Replace sort implementations](https://github.com/rust-lang/rust/pull/124032)

Release blog section (if any, leave blank if no section is expected):

[workingjubilee]

cc @Voultapher @orlp if you want to have input on the relnotes here.

[joshtriplett]

Sketch for the compatibility aspect (not covering the details of the performance improvement):

The implementations of sort functions (sort, sort_by, sort_by_cached_key, sort_by_key, sort_unstable, sort_unstable_by, sort_unstable_by_key) now have higher performance. These functions may now panic if the implementation of Ord or the supplied comparison function is not a total order.

[Voultapher]

select_nth_unstable, select_nth_unstable_by and select_nth_unstable_by_key are also affected. Though we expect to see less impactful performance differences on x86-64, Arm however should see larger improvements as it sees larger improvements for the new unstable partition code.

[Voultapher]

Regarding how to communicate the performance improvements, saying ~2x for both stable and unstable sort is somewhat based in reality, however I'd much prefer not to mention a single number x or % improvement, as that depends on the input pattern, input length and input type, and we see in our testing changes ranging from no change at all, all the way up to 17x faster execution. I'd rather we say that the performance improved significantly and link to the relevant section in the design documents that explains our methodology and results for evaluating the change in performance slice::sort and slice::sort_unstable.

[workingjubilee]

Should probably use these permalinks specifically:

• https://github.com/Voultapher/sort-research-rs/blob/28d0cf339f123bf34b3a2dcea4f5d52e1867cfe3/writeup/driftsort_introduction/text.md#efficient
• https://github.com/Voultapher/sort-research-rs/blob/28d0cf339f123bf34b3a2dcea4f5d52e1867cfe3/writeup/ipnsort_introduction/text.md#efficient

[the8472]

Do we have any source of randomness in the unstable sort to ensure it's really unstable (like hashmaps)? If not the compat note could also mention that the order changed in case someone accidentally relied on it.

[workingjubilee]

No, we do not, it's deterministic within a version.

[workingjubilee]

...and yes, it was in fact the case that someone asserted on this order in a test and the test was regressed as a result.

[orlp]

No, we do not, it's deterministic within a version.

We do right now. I don't know if we actually guarantee this, and perhaps we could in the future use randomness for e.g. pivot selection. It's a bit weird because the current stable "current implementation" notes mention determinism, but.. well, it's in the "current implementation" section, not general guarantees.

[Voultapher]

Should probably use these permalinks specifically:

It can be useful to have the ability to fix typos. I plan on keeping these links stable.

[Amanieu]

This has been included in the release notes and libs is satisfied with the wording, closing.