Most relevant element of what's going on here is that Rust's standard library is deliberately split three ways: Core has stuff that should "just work" on your target platform, Alloc adds stuff that further requires a Memory Allocator, which is something target hardware doesn't come with, but any non-trivial system is likely to build, then Std adds stuff which requires an Operating System, such as Files, and Threading

C is technically also split, so called "freestanding" C implementations don't provide features like stdio but they do have e.g. math functions. C++ attempts something similar but it's a bit hit-and-miss as a truly "free standing" C++ doesn't entirely make sense, as systems that try to use C++ for very low level work often discover.

The next less relevant observation is that Rust chooses to call these sort and sort_unstable - the one that's guaranteed to be available doesn't get the easier name, that's reserved for the one that definitely doesn't have unexpected behaviour. If you don't know what an "unstable" sort is, then sort_unstable's behaviour might in some cases be astonishing. Some languages make the opposite choice, which means programmers may use sort, not realising it's actually an unstable sort because the entire concept was never explained to them.

This is one of many examples of Rust's safety achieved not via some sophisticated technology but just by thinking about why people screw up. Every Rust programmer who without thinking writes sort gets a stable sort, if that was too slow, they can choose sort_unstable, but doing so prompts them to consider, wait, is an unstable sort correct here?

Finally the least relevant but hopefully still interesting observation is that it is quite possible to have a stable sort which doesn't require allocation, but the performance is not so hot. It seems pretty unlikely that you must have a stable sort and you can't afford an allocator and yet you don't mind the performance hit. As I understand it though some C++ libraries do offer this.

So you're not wrong, but also, the Linux kernel uses a modified variant of alloc, so not only can it use sort_unstable, it also has access to sort https://github.com/torvalds/linux/blob/2d1bcbc6cd703e64caf8d...