Counting sort using STL
Associative container

Update: Because of the O(n.log(n)) nature of std::map we have concluded this is not a good idea (But it was worth the test).

Rather than using a vector to store the count you can use an associative container.

std::vector&lt;std::size_t&gt; counts(max - min + 1, 0);

// replace with 

using ValueType = std::iterator_traits&lt;InputIterator&gt;::value_type;
std::map&lt;ValueType, std::size_t&gt;  counts;



This will limit the amount of memory you use otherwise the amount of space you use could potentially exceed memory.
Also iterating over a sparse array would be expensive (As there will be lots of zero counts). By using an associative container you only iterate over valid values.


Range based for

Use the new range based for.

for (auto it_c = counts.begin(); it_c != counts.end(); ++it_c) {

// replace with:

for(auto const&amp; value: counts) {


Combine range based for and associative containers

void counting_sort(InputIterator first, InputIterator last)
{
    using ValueType = std::iterator_traits&lt;InputIterator&gt;::value_type;
    std::map&lt;ValueType, std::size_t&gt; counts;

    for(auto value: boost::make_iterator_range(first, last)) { 
        ++counts[value];
    }

    for(auto count: counts) {
        ValueType&amp;   value = count.first;
        std::size_t&amp; size  = count.second;  
        std::fill_n(first, size, value);
        std::advance(first, size);
    }
}