Counting sort.

counting_sort.cpp

template <class T>
auto countingSort(const std::vector<T>& vec)
{
    if(vec.size() <= 1) std::move(vec);
    
    std::vector<T> counts(vec.size(), 0);
    
    const auto size = vec.size();
    for(size_t i = 0; i < size - 1; ++i)
    {
        for(size_t j = i + 1; j < size; j++)
        {
            if(vec[i] < vec[j])
            {
                ++counts[j];
            }
            else if(vec[i] > vec[j])
            {
                ++counts[i];
            }
        }
    }
    
    std::vector<T> result(vec.size());
    for(size_t i = 0; i < size; ++i)
    {
        result[counts[i]] = vec[i];
    }
    
    return std::move(result);
}

int main()
{
    std::vector<int> vec {-4, 3, 1, -6, -1, -9, 3, 5, 12, 64, 23, 4, 12 };
    auto result = countingSort(vec);
    
    for(const auto& item: result)
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';

    return 0;
}