For what inputs is `std::sort`

unstable?

`std::sort`

unstable?A sorting algorithm is “stable” if, for two equivalent elements, it preserves their
original order relative to each other.
It might be useful to know a concrete example of input for which your library’s
`std::sort`

is unstable. Here are examples for libc++ and libstdc++ (as of September 2020).
Godbolt.

```
auto LessMod2 = [](int a, int b) {
return (a % 2) < (b % 2);
};
// For libc++:
std::vector<int> v1 = {
0, 1, 0, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3,
};
std::sort(v1.begin(), v1.end(), LessMod2);
// 0 2 0 1 1 ... 1 1 3
```

The above 31-element input sorts unstably for both libc++ and libstdc++. However, libstdc++ also sorts the following 17-element input unstably:

```
// For libstdc++:
std::vector<int> v2 = {
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 3,
};
std::sort(v2.begin(), v2.end(), LessMod2);
// 1 3 1 1 ... 1 1 1
```

As of September 2020, it appears that libc++ `std::sort`

happens to be stable for all
ranges of size less than 31, and libstdc++ `std::sort`

happens to be stable for all
ranges of size less than 17. (Do not rely on this little factoid in production!)

To be clear: There’s nothing wrong with this. As the caller, if you want stable sorting,
you should use `std::stable_sort`

, not `std::sort`

.

As the vendor, if you don’t intend to guarantee stability, it might be a *good* idea
to break stability for small inputs, just to teach your users not to depend on that
property by accident or coincidence.

Notice that by definition, `std::stable_sort`

never permutes a range that is already sorted.

```
auto orig = x;
if (std::is_sorted(x.begin(), x.end(), comp)) {
std::stable_sort(x.begin(), x.end(), comp);
}
assert(x == orig);
```

I find it interesting that libstdc++’s `std::sort`

*will* permute a sorted range;
notice that the example input `v2`

is trivially sorted, and yet libstdc++’s `std::sort`

swaps some of the elements. I’m not sure whether libc++’s `std::sort`

will ever
permute a sorted range.