Using counting_sort to improve integer_spread_sort #11
Description
Hi, it's me again :)
No bug or memory leak today, but I was benchmarking some sorting algorithms again and was surprised by how fast a simple counting sort. Here are the results of a benchmark testing several sorting algorithms against collections of one million of integer elements with several data distributions:
While not always the fastest, counting sort tends to be insanely fast and always beats spreadsort in the benchmarks. Of course, counting sort has its share of problems, but I believe that it can be used to improve the integer-only version of spreadsort that does not take any custom comparison or shift function. Basically, we could add the following implementation somewhere (this version uses C++11, but it can be done in C++03):
template<class ForwardIter, class T>
void counting_sort(ForwardIter first, ForwardIter last, T min, T max) {
if (min == max) return;
using difference_type = typename std::iterator_traits<ForwardIterator>::difference_type;
std::vector<difference_type> counts(max - min + 1, 0);
for (auto it = first ; it != last ; ++it) {
++counts[*it - min];
}
for (auto count: counts) {
first = std::fill_n(first, count, min++);
}
}
Then we could modify the beginning of spreadsort_rec to use it as follows:
template <class RandomAccessIter, class Div_type, class Size_type>
inline void
spreadsort_rec(RandomAccessIter first, RandomAccessIter last,
std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
, size_t *bin_sizes)
{
//This step is roughly 10% of runtime, but it helps avoid worst-case
//behavior and improve behavior with real data
//If you know the maximum and minimum ahead of time, you can pass those
//values in and skip this step for the first iteration
RandomAccessIter max, min;
if (is_sorted_or_find_extremes(first, last, max, min))
return;
if (*max - *min <= last - first) {
counting_sort(first, last, *min, *max);
return;
}
// Rest of the current implementation...
}
Thanks to is_sorted_or_find_extremes, we already know the minimum and maximum values of the range [first, last), so we don't have to compute them again in counting_sort. The check *max - *min <= last - first ensures that counting_sort will be called only if the std::vector it needs to allocate is no bigger than the original array, which means that spreadsort keeps a O(n) auxiliary memory guarantee (IIRC it is the current memory guarantee of spreadsort, right?). That check also ensures that the algorithm won't even run into the pathological worst cases of counting sort, so we only keep the good parts.
In other words, we can significantly speed up some scenarios at the cost of a single condition that shouldn't even weight too much when it fails. If I find the time, I will try to compare a version of spreadsort with this trick against the current one and share the benchmark results here.
