Consider a drastic change of interface - instead of sorting elements in-place, it might be better to return a histogram object with vector-like access:
histogram sorted(const std::input_range& auto nums);
We could implement the histogram as
#include <iterator>
#include <numeric>
#include <ranges>
// Special case histogram class that counts values that are 0, 1 or 2.
class histogram_012
{
std::array<std::size_t,3> count{{ 0, 0, 0 }};
public:
struct const_iterator
{
using difference_type = std::ptrdiff_t;
using value_type = int;
using pointer = int*;
using reference = int&;
using iterator_category = std::input_iterator_tag;
const histogram_012 *p;
std::size_t pos;
constexpr auto operator<=>(const const_iterator& other) const = default;
const_iterator& operator++()
{
++pos; return *this;
}
auto operator*() const
{
// This is just for exposition; it's not efficient
auto n = pos;
int i = 0;
for (auto c: p->count) {
if (n < c) { return i; }
n -= c;
++i;
}
// out-of-range (undefined)
return 0;
}
};
template<std::ranges::input_range C>
requires std::is_same_v<int, std::ranges::range_value_t<C>>
explicit constexpr histogram_012(C const& nums)
{
for (int n: nums) {
count[0] += (n == 0);
count[1] += (n == 1);
count[2] += (n == 2);
}
}
// Minimal container interface - this needs completing
constexpr auto size() const { return std::accumulate(count.begin(), count.end(), std::size_t{}); }
constexpr const_iterator begin() const { return {this, 0}; }
constexpr const_iterator end() const { return {this, size()}; }
};
and sorted() as
auto sorted(auto const& nums) { return histogram_012{nums}; }
Simple demo:
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
int main()
{
std::vector<int> values = {0,2,1,2,1};
auto const sorted_values = sorted(values);
std::copy(sorted_values.begin(), sorted_values.end(),
std::ostream_iterator<int>(std::cout, ", "));
std::cout << '\n';
}
Credit to Peter Cordes for suggesting this approach, in comments to other answers.
