Return to Revisions

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 :)

However, while keeping the spirit and simplicity of counting sort, there are still several small things you can do to make it better:

• 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.