Why is libstdc++ `std::sort` not excluding the pivot from its to sub-ranges?

Viewed 92

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_pivot that does a little different than std::partition... but I don't see how it works and why it would be better than just std::partition and this suggested +1. Any idea or references?

Side notes:

  • The libstdc++ std::sort implementation 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
0 Answers
Related