The implementation of libstdc++ std::sort is the following (taken from here)
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
void
__introsort_loop(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Size __depth_limit, _Compare __comp)
{
while (__last - __first > int(_S_threshold))
{
if (__depth_limit == 0)
{
std::__partial_sort(__first, __last, __last, __comp);
return;
}
--__depth_limit;
_RandomAccessIterator __cut = std::__unguarded_partition_pivot(__first, __last, __comp);
std::__introsort_loop(__cut, __last, __depth_limit, __comp);
__last = __cut;
}
}
Let us simplify it a bit to make it clearer:
- remove the standard library mandatory underscores
- remove the introsort part (fallback to heapsort if too many levels, not our subject here)
- remove insertion sort optimization for small arrays
- replace the loop with a second recursive call
If I am not mistaken, we then have this:
template<typename RandomAccessIterator, typename Size, typename Compare>
void
quicksort_loop(RandomAccessIterator first,
RandomAccessIterator last,
Compare comp)
{
if (last - first > 1)
{
auto cut = std::__unguarded_partition_pivot(first, last, comp);
std::quicksort_loop(first, cut, comp);
std::quicksort_loop(cut, last, comp);
}
}
But *cut is supposed to hold the pivot, right? So why is it included into the second sub-range? I would have expected something like:
template<typename RandomAccessIterator, typename Size, typename Compare>
void
quicksort_loop(RandomAccessIterator first,
RandomAccessIterator last,
Compare comp)
{
if (last - first > 1)
{
auto pivot = choose_pivot(first,last,comp); // e.g. median-of-three
auto cut = std::partition(first, last, [&](auto&& x){ return x<pivot; });
std::quicksort_loop(first, cut, comp);
std::quicksort_loop(cut+1, last, comp); // Note the +1
}
}
- How do we ensure that the algorithm terminates if there is no
+1? If we repeatedly take a bad pivot then the first sub-range can be empty and the other would be the whole range. - I guess the magic comes from
std::__unguarded_partition_pivotthat does a little different thanstd::partition... but I don't see how it works and why it would be better than juststd::partitionand this suggested+1. Any idea or references?
Side notes:
- The libstdc++
std::sortimplementation comes directly from the original STL and it was already written this way back then (more or less). - The Microsoft version does something very similar to what I am proposing, but it uses a three-way partition that returns two iterators with all elements equal to the pivot between them. See here.
- Regarding
libc++, I really don't know what is going on, the code is 100 times more complicated :D