Counting sort using STL I'm trying to learn to use the C++ Standard Library and some of the modern C++11 features. Can someone review my counting sort algorithm below and critique my style/algorithm/use of the STL? Thank you!

#include &lt;algorithm&gt;
#include &lt;chrono&gt;
#include &lt;iostream&gt;
#include &lt;iterator&gt;
#include &lt;random&gt;
#include &lt;vector&gt;

const int kSize = 100000000;      // Size of container to sort
const int kRangeFrom = -1000000;  // first of range for random number generator
const int kRangeTo = 1000000;     // last of range for random number generator

// Linear time sorting algorithm for integers
template&lt;typename InputIterator&gt;
void counting_sort(InputIterator first, InputIterator last) {
  auto minmax_el = std::minmax_element(first, last);
  auto min = *minmax_el.first;
  auto max = *minmax_el.second;
  std::vector&lt;std::size_t&gt; counts(max - min + 1, 0);

  std::for_each(first, last, [&amp;](auto x) { 
    ++counts[x - min];  // Store value counts
  }); 

  for (auto it_c = counts.begin(); it_c != counts.end(); ++it_c) { 
    auto idx = std::distance(counts.begin(), it_c);
    std::fill_n(first, *it_c, idx + min); // Store in sorted order
    std::advance(first, *it_c);
  }
}

int main() {
  std::random_device rd;
  std::mt19937 mt(rd());
  std::uniform_int_distribution&lt;int&gt; dist(kRangeFrom,kRangeTo);

  std::vector&lt;int&gt; v1(kSize);
  std::generate(v1.begin(), v1.end(), [&amp;](){ return dist(mt); });

  std::vector&lt;int&gt; v2(kSize);
  std::copy(v1.begin(), v1.end(), v2.begin());

  auto first1 = std::chrono::steady_clock::now();
  counting_sort(v1.begin(), v1.end());
  auto last1 = std::chrono::steady_clock::now();

  auto first2 = std::chrono::steady_clock::now();
  std::sort(v2.begin(), v2.end());
  auto last2 = std::chrono::steady_clock::now();

  std::cout &lt;&lt; "counting sort time: " &lt;&lt; std::chrono::duration&lt;double, std::milli&gt;(last1 - first1).count() &lt;&lt; " ms" &lt;&lt; '\n';
  std::cout &lt;&lt; "std::sort time: " &lt;&lt; std::chrono::duration&lt;double, std::milli&gt;(last2 - first2).count() &lt;&lt; " ms" &lt;&lt; '\n';
  std::cout &lt;&lt; "v1 == v2: " &lt;&lt; std::equal(v1.begin(), v1.end(), v2.begin()) &lt;&lt; '\n';

  return 0;
}
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);
    }
}