Changing std:sort at Google’s scale and beyond
Fun safety problems.<p>Towards the end of this post, the author mentions a bunch of places where std::sort() blows up if your data or your sort rule doesn&#x27;t exhibit strict weak ordering. In some cases you get a bad sort, which feels fair enough since you violated the rules the sort algorithm is relying on, but in others it literally has Undefined Behaviour in C++.<p>Notably Rust&#x27;s sort() and unstable_sort() do not have this problem, because of course these are safe Rust, and safe Rust doesn&#x27;t have Undefined Behaviour. But why can this work?<p>First up, one bullet which gets dodged is that Rust&#x27;s floating point types (f32 and f64) are not Ord. Rust acknowledges that NaN != NaN and therefore we can&#x27;t expect to go around sorting a slice of floating point values. In C++ that&#x27;s on the programmer, in C++ the fact you can write a &lt; b means that type counts as ordered, even though it trivially isn&#x27;t for several built-in types. So if you simply naively try to sort an [f32] Rust says you can&#x27;t because it isn&#x27;t Ord, you will need to write a lambda or whatever to Order these f32s and then if some of them are NaN your lambda is responsible for deciding what to do about that.<p>But even if we insist on getting in harm&#x27;s way, safe Rust promises to protect us anyway. For example if I make an array of a thousand misfortunate::OnewayGreater&lt;u8&gt;s they&#x27;re only one byte each, yet they all insist they&#x27;re Ordered greater than each other and even than themselves, Rust&#x27;s sort() doesn&#x27;t cause Undefined Behaviour on this input. It may never succeed, since all the elements to be &quot;sorted&quot; insist they&#x27;re greater than each other, but it definitely won&#x27;t segfault, trash unrelated memory or cause chaos.