Use sort_unstable to sort primitive types

[ChrisJefferson]

When sorting primitive types, without a sort_by function, sort and sort_unstable produce the same output (because the "identical elements" are themselves indistinguishable).

This change was done by hand ( #76541 ), and clippy will recommend changing sort to sort_unstable on primitive types.

However, if it is so useful it feels like it should be easy to do within the standard library itself, if there is a trait (or a trait was added) for primitive types.

This feel preferably to the current situation, where clippy tells users to change it, as then (see #76541 for example ), users have to keep adding comments to remind themselves that the sort_unstable is actually stable in this case.

[clarfonthey]

Is sort_unstable actually guaranteed to be better, though? I thought that the main use case was to avoid allocating for embedded environments.

[ChrisJefferson]

Usually a quicksort/pdqsort will be faster than a mergesort/timsort. Both have code in them to handle partially sorted data. It can't be "guaranteed", because the algorithms are so different. Also, some changes like this were already done in #76541 .

[clarfonthey]

Yeah, my point is that I don't think that really anything is guaranteed about sort_unstable besides a lack of allocation and hence it might not be the best to blanket suggest it.

Is sort_unstable actually guaranteed to be better, though? I thought that the main use case was to avoid allocating for embedded environments.

No, the current stable sort can be 10 times faster than the current unstable sort. But often it's the opposite: unstable sort is 10 times faster than stable sort. It really depends on the data and we can only compare sorting algorithms for the same given data.