Implement quicksort on bi-directional iterators

Question

It seems quite straightforward to implement quicksort using bi-directional iterators with O(NlgN) time and O(lgN) space. So, what is the particular reason that std::sort() requires random-access iterators?

I have read about the topic why do std::sort and partial_sort require random-access iterators?. But it doesn't explain in what specific part of a possible std::sort() implementation that may actually require a random-access iterator to maintain its time and space complexity.

A possible implementation with O(NlgN) time and O(lgN) space:

template <typename BidirIt, typename Pred>
BidirIt partition(BidirIt first, BidirIt last, Pred pred) {
  while (true) {
    while (true) {
      if (first == last) return first;
      if (! pred(*first)) break;
      ++first;
    }
    while (true) {
      if (first == --last) return first;
      if (pred(*last)) break;
    }
    iter_swap(first, last);
    ++first;
  }
}

template <typename BidirIt, typename Less = std::less<void>>
void sort(BidirIt first, BidirIt last, Less&& less = Less{}) {
  using value_type = typename std::iterator_traits<BidirIt>::value_type;
  using pair = std::pair<BidirIt, BidirIt>;
  std::stack<pair> stk;
  stk.emplace(first, last);
  while (stk.size()) {
    std::tie(first, last) = stk.top();
    stk.pop();
    if (first == last) continue;
    auto prev_last = std::prev(last);
    auto pivot = *prev_last;
    auto mid = ::partition(first, prev_last,
      [=](const value_type& val) {
        return val < pivot;
      });
    std::iter_swap(mid, prev_last);
    stk.emplace(first, mid);
    stk.emplace(++mid, last);
  }
}

Answer 1

There are a few reasons why practical library sort functions need random access iterators.

The most obvious one is the well-known fact that choosing an endpoint of the partition for a pivot reduces quicksort to O(n²) if the data is sorted (or "mostly sorted"), so most real-life quicksort's actually use a more robust algorithm. I think the most common one is the Wirth algorithm: choose the median of the first, middle, and last element of the partition, which is robust against sorted vectors. (As Dieter Kühl points out, just selecting the middle element would work almost as well, but there is practically no extra cost for the median-of-three algorithm.) Selecting a random element would also be a good strategy, since it is harder to game, but the requirement for a PRNG might be discouraging. Any strategy for selecting the pivot other than taking an endpoint requires random-access iterators (or a linear scan).

Second, quicksort is sub-optimal when the partition is small (for some heuristic definition of small). When there are few enough elements, the simplified loop of an insertion sort combined with locality of reference will make that a better solution. (This doesn't affect the complexity of the overall algorithm because the threshold is a fixed size; insertion sort of a maximum of k elements is O(1) for any previously established k. I think you'll typically find values between 10 and 30.) The insertion sort can be done with bidirectional iterators, but figuring out if the partition is smaller than the threshold cannot (again, unless you use an unnecessarily slow loop).

Third and possibly most importantly, quicksort can degenerate into O(n²) no matter how hard you try. Earlier C++ standards accepted that std::sort might be "O(n log n) on the average", but since the acceptance of DR713 the standard requires std::sort to be O(n log n) without qualifications. This cannot be achieved with a pure quicksort, so modern library sort algorithms are actually based on introsort or similar. This algorithm falls back to a different sorting algorithm -- normally heapsort -- if it detects that the partitioning is too biased. The fallback algorithm is very likely to require random access iterators (heapsort and shellsort both do, for example).

Finally, recursion depth can be reduced to a maximum of log₂n by using the simple strategy of recursing on the smallest partition and tail-recurring (explicitly looping) on the larger partition. Since recursion is generally faster than explicitly maintaining a stack, and recursion is totally reasonable if the maximum recursion depth is in the low two digits, this little optimization is worthwhile (although not all library implementations use it.) Again, that requires being able to compute the size of the partitions.

There are probably other aspects of practical sortation which require random access iterators; those are just off the top of my head.

Answer 2

The simple answer is that quicksort is slow unless optimized in particular for small ranges. To detect ranges are small, an efficient way to determine their size is needed.

I have a presentation (here are the slides and the code) where I show the steps used to create a fast implementation of quicksort. It turns out that the sort implementation is actually a hybrid algorithm.

The essential steps in making quicksort fast are the following:

1. Guard against [mostly] sorted sequences. One of the interesting cases here is actually the special sorted sequence consisting of all identical elements: in real data equal subsequences are not rare at all. The approach to do so is monitoring when quicksort does too much work and switching to an algorithm with known complexity like heapsort or mergesort to finish sorting the problematic subsequence. This approach goes under the name introsort.
2. Quicksort is really bad on short sequences. Since quicksort is a divide and conquer algorithm it actually produces many small sequences. Dealing with small sequences can, e.g., be done using insertionsort. To find out whether a sequence is small it is necessary to check the size of sequences efficiently. This is where the need for random access comes in.

3. There are a number of additional optimization which are necessary to make quicksort really fast although their impact is overall smaller than the impact of the approaches above. For example:

   • The used partition needs to take advantages of sentinels to reduce the number of comparisons.
   • Observing whether the partition does any work can lead to an early bail-out by gambling on running an insertionsort which stops when doing too much work.
   • To increase the chances of the previous point using the midpoint rather than either end of the sequence to be sorted as pivot has an advantage (this also requires random access but is a comparatively small reason).

I haven't done the experiment but implementing these necessary optimizations for bidirectional iterators is probably not really effective: the cost of determining whether a sequence is small (which doesn't need to get the size of the sequence but can stop as soon as it is clear that the sequence is not small) probably becomes to high. If quicksort becomes impeded to run just about 20% slower, using a different sort algorithm is preferable: using, e.g., mergesort is roughly in that range and can has the advantage that it can also be stable.

BTW, the fabled choice of the median as a pivot doesn't seem to have any interesting impact: using the middle value rather than the median seems to be roughly as good (but it is, indeed a better choice than either end).