Return to Answer

Counting sort is an excellent tool when you know that you will be sorting integer values in a tight range, so I would keep it as is with its « problems » instead of trying to turn it in a more generic algorithm. If you want a more flexible integer sorting algorithm, radix sort would be the way to go :)

• InputIterator is never a suitable iterator category for an inplace sorting algorithm since input iterators are single-pass, which means that it's not guaranteed that you can write values back into them once you have read them. Your counting_sort implementation even reads the iterated values several times. The iterator category you want is ForwardIterator.

• You can save memory and return early when the original collection is already sorted: while the standard library does not provide such a function (it's too specific), it is possible to perform std::minmax_element and std::is_sorted at once without additional cost. However, you can find such a function in Boost.Sort spreadsort implementation:

   template <class RandomAccessIter>
   inline bool
   is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last,
   RandomAccessIter & max, RandomAccessIter & min)
   {
   min = max = current;
   //This assumes we have more than 1 element based on prior checks.
   while (!(*(current + 1) < *current)) {
   //If everything is in sorted order, return
   if (++current == last - 1)
   return true;
   }
   //The maximum is the last sorted element
   max = current;
   //Start from the first unsorted element
   while (++current < last) {
   if (*max < *current)
   max = current;
   else if (*current < *min)
   min = current;
   }
   return false;
   }
  

  Just make sure beforehand that std::distance(first, last) > 0 if you don't want surprises due to dereferencing iterators that theoretically point to nowhere.

• std::advance is \$O(n)\$ for forward iterators and bidirectional iterators, which means that if you want to sort an std::list or an std::forward_list with your counting_sort, you will end advancing twice the same iterator in \$O(n)\$ with the following lines:

   std::fill_n(first, size, value);
   std::advance(first, size);
  

  This is a waste of time since std::fill_n has already computed the iterator where to advance first internally. Fortunately, since C++11, std::fill_n returns the iterator past the last element assigned, so you can simply turn the two lines above into a single more efficient one:

   first = std::fill_n(first, size, value);
  

  Now counting_sort should be a bit more efficient when given forward or bidirectional iterators.

Counting sort is an excellent tool when you know that you will be sorting integer values in a tight range, so I would keep it as is with its « problems » instead of trying to turn it into a more generic algorithm. If you want a more flexible integer sorting algorithm, radix sort would be the way to go :)

• InputIterator is never a suitable iterator category for an inplace sorting algorithm since input iterators are single-pass, which means that it's not guaranteed that you can write values back into them once you have read them. Your counting_sort implementation even reads the iterated values several times. The iterator category you want is ForwardIterator.

  Note: it might be a mere hint for the reader today, but this kind of thing will be even more meaningful when concepts will be included into the language.

• You can return early and save memory when the original collection is already sorted: while the standard library does not provide such a function (it's too specific), it is possible to perform std::minmax_element and std::is_sorted at once without any significant additional cost. You can find such a function in Boost.Sort spreadsort implementation:

   template <class RandomAccessIter>
   inline bool
   is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last,
   RandomAccessIter & max, RandomAccessIter & min)
   {
   min = max = current;
   //This assumes we have more than 1 element based on prior checks.
   while (!(*(current + 1) < *current)) {
   //If everything is in sorted order, return
   if (++current == last - 1)
   return true;
   }
   //The maximum is the last sorted element
   max = current;
   //Start from the first unsorted element
   while (++current < last) {
   if (*max < *current)
   max = current;
   else if (*current < *min)
   min = current;
   }
   return false;
   }
  

  Just make sure beforehand that fist != last if you don't want surprises due to dereferencing iterators that theoretically point to nowhere.

• std::advance is \$O(n)\$ for forward iterators and bidirectional iterators, which means that if you want to sort an std::list or an std::forward_list with your counting_sort, you will end advancing twice the same iterator in \$O(n)\$ with the following lines:

   std::fill_n(first, size, value);
   std::advance(first, size);
  

  This is a waste of time since std::fill_n has already computed the iterator where to advance first internally. Fortunately, since C++11, std::fill_n returns the iterator past the last element assigned, so you can simply turn the two lines above into a single more efficient one:

   first = std::fill_n(first, size, value);
  

  Now counting_sort should be a bit more efficient when given forward or bidirectional iterators.

• A common advice with lambdas is to capture only what you need (instead of everything) to make sure that you won't capture an unwanted variable by error when refactoring:

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

  Anyway, @Loki's advice holds here: you can use a range-based for loop instead of std::for_each.

• You can save memory and return early when the original collection is already sorted: while the standard library does not provide such a function (it's too specific), it is possible to perform std::minmax_element and std::is_sorted at once without additional cost. However, you can find such a function in Boost.Sort spreadsort implementation:

   template <class RandomAccessIter>
   inline bool
   is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last,
   RandomAccessIter & max, RandomAccessIter & min)
   {
   min = max = current;
   //This assumes we have more than 1 element based on prior checks.
   while (!(*(current + 1) < *current)) {
   //If everything is in sorted order, return
   if (++current == last - 1)
   return true;
   }
   //The maximum is the last sorted element
   max = current;
   //Start from the first unsorted element
   while (++current < last) {
   if (*max < *current)
   max = current;
   else if (*current < *min)
   min = current;
   }
   return false;
   }
  

  Just make sure beforehand that std::distance(first, last) > 0 if you don't want surprises due to dereferencing iterators that theoretically point to nowhere.

• InputIterator is never a suitable iterator category for an inplace sorting algorithm since input iterators are single-pass, which means that it's not guaranteed that you can write values back into them once you have read them. Your counting_sort implementation even reads the iterated values several times. The iterator category you want is ForwardIterator.

• InputIterator is never a suitable iterator category for an inplace sorting algorithm since input iterators are single-pass, which means that it's not guaranteed that you can write values back into them once you have read them. Your counting_sort implementation even reads the iterated values several times. The iterator category you want is ForwardIterator.

• You can save memory and return early when the original collection is already sorted: while the standard library does not provide such a function (it's too specific), it is possible to perform std::minmax_element and std::is_sorted at once without additional cost. However, you can find such a function in Boost.Sort spreadsort implementation:

   template <class RandomAccessIter>
   inline bool
   is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last,
   RandomAccessIter & max, RandomAccessIter & min)
   {
   min = max = current;
   //This assumes we have more than 1 element based on prior checks.
   while (!(*(current + 1) < *current)) {
   //If everything is in sorted order, return
   if (++current == last - 1)
   return true;
   }
   //The maximum is the last sorted element
   max = current;
   //Start from the first unsorted element
   while (++current < last) {
   if (*max < *current)
   max = current;
   else if (*current < *min)
   min = current;
   }
   return false;
   }
  

  Just make sure beforehand that std::distance(first, last) > 0 if you don't want surprises due to dereferencing iterators that theoretically point to nowhere.

• std::advance is \$O(n)\$ for forward iterators and bidirectional iterators, which means that if you want to sort an std::list or an std::forward_list with your counting_sort, you will end advancing twice the same iterator in \$O(n)\$ with the following lines:

   std::fill_n(first, size, value);
   std::advance(first, size);
  

  This is a waste of time since std::fill_n has already computed the iterator where to advance first internally. Fortunately, since C++11, std::fill_n returns the iterator past the last element assigned, so you can simply turn the two lines above into a single more efficient one:

   first = std::fill_n(first, size, value);
  

  Now counting_sort should be a bit more efficient when given forward or bidirectional iterators.