In this post I wrote about implementing the quicksort algorithm in C++ compared to Python. In the sence of simplicity it was neither optimized nor using any STL algorithms. This I want to change with this article.

While the biggest limitation there was that only contiguous container could be used, it was also using three loops, 2 of them nested in another. The solution for both of this problems is changing the partitioning algorithm (there is already one available at the STL, but I’ll come to it later).

The pivot in the quicksort algorithm is nothing else than a partition border: all values lower than the pivot are moved left to the pivot, all greater right to it - as result the container is partitioned into two halfes.

The standard algorithm is to iterate left and right simultaneously and swap the values according to their relationship to the pivot:

2 5 1 A 3 6 ( 4 ) 2 3 1 B 5 6 ( 4 ) 2 3 1 C ( 4 ) 6 5 2 3 1 ( D 4 ) 6 5

In this example A is the initial container. Step B swaps 5 (greater the the pivot) and 3 (smaller than the pivot). In the final Step C 5 and 4 got swapped so that the pivot 4 is at the pivot point which splits the two parts. D shows the both partitions.

As told, one of the disadvantage of this algorithm is that the iterators of the supported containers have to be bidirectional (in the concrete example also contiguous due to using the less-than comparison on the iterators).

But there is a simpler way which requires only two loops not nested loops. The basic principle is to start from left and left + i and then swap each element which is less than the pivot. At each swap left is increased (loop 1). The only condition is that left has to start at the at the first value in the container which is not less the pivot (this is the second loop).

2 5 1 A 3 6 ( 4 ) 2 5 1 B 3 6 ( 4 ) 2 1 5 C 3 6 ( 4 ) 2 1 3 D 5 6 ( 4 ) 2 1 3 E 5 6 ( 4 )

Here starting point is also A. In Step B the first element which is not less then pivot is searched, this is 5. From this point on the forward iteration is started, left is at 5, right is at left + 1 which is 1 - this happens at step C. Because left (5) is greater than the pivot 4, the swap is performed and both left and right are increased. In Step D the same again, 5 (left) is swapped with 3 (right), both are increased. In the following steps left stays at its position (pointing to 3) and only right gets increased. Since no value less than the pivot 4 follows, no further swaps will be made.

The result in step E is the same in terms of partitioning as in the first algorithm: the values less than the pivot are on the left, all others on the right. The only difference: the pivot element itself isn’t placed at the partition border, but that’s not problematic for this algorithm.

One notible advantage of this algorithm is that the iterators must not point to a contiguous container, nearly all types of writable containers can be sorted this way.
At least forward iterators and less-than comparable elements in it are required.

Now lets see how it could be implemented:

void _swap(auto left, auto right) {
    auto tmp = *left;
    *left = *right;
    *right = tmp;
}

auto _partition(auto start, auto end, auto pivot) {
    // find the first element not smaller than pivot
    while (start != end && *start < pivot) { ++start; }
    // non is equal or greater than the pivot - return end (= start)
    if (start != end) {
        // now start comparing start with start + x
        for(auto pos = std::next(start); pos != end; ++pos) {
            if (*pos < pivot) {
                // current item at pos is smaller than pivot - swap with the one at `start`
                _swap(start, pos);
                ++start;
            }
        }
    }
    // at least return the iterator either at end (only one partition)
    // or at the point where the partition with the values equal to or greater than pivot 
    return start;
}

This looks a lot nicer than the partitioning algorithm in this post!
Of course the quicksort function itself also gets easier:

void quicksort(auto left, auto right) {
    if (!std::is_sorted(left, right)) {
        // take the pivot from the leftmost element
        auto pivot = *left; 
        // get the partitioning point
        auto part_it = _partition(left, right, pivot);
        if (part_it != left) {
          // and call the quicksort for left only if the partitioning point isn't at leftmost position
          quicksort(left, part_it);
        }
        else {
          // the partitioning point is at leftmost position, go behind it to avoid an endless recursion
          part_it = std::next(part_it);
        }
        // and right partition recursivly.
        quicksort(std::next(part_it), right);
    }
}

The first condition checks if the values in range of the given iterators are already sorted.
This also returns true if the range contains no elements, so we don’t have to check for left != right.

But - this could get much more easier, the STL has a lot more algorithms which could help us.
At first lets replace the _swap function by using std::iter_swap.

            if (*pos < pivot) {
                std::iter_swap(start, pos);
                ++start;
            }

For finding the first element not smaller than pivot we could use one of the find algorithms: std::find_if_not. This takes a start and end iterator, and a predicate telling which returns what to find:

// while (start != end && *start < pivot) { ++start; }
start = std::find_if_not(start, end, [&pivot](const auto& item){
    return std::less(item, pivot);
});

Take a look at the partitioning algorithm so far:

auto _partition(auto start, auto end, auto pivot) {
    // find the first element not smaller than pivot
    start = std::find_if_not(start, end, [&pivot](const auto& item){
        return std::less(item, pivot);
    });

    // non is equal or greater than the pivot - return end (= start)
    if (start != end) {
        // now start comparing start with start + x
        for(auto pos = std::next(start);pos != end;++pos) {
            if (!std::less(*pos*, pivot)) {
                // current item at pos is smaller than pivot - swap
                std::iter_swap(start, pos);
                ++start;
            }
        }
    }
    // at least return the iterator either at end (only one partition)
    // or at the point where the partition with the values equal to or greater than pivot 
    return start;
}

But - there is a much more easier way: the stl itself already defines a partitioning algorithm: std::partition.

This does exactly the same as the algorithm above (probably much better) except that it takes a predicate to decide what value goes to left or right partition.
So we can left out not only the _swap but also the _partition function.
This is what remains:

# include <algorithm>
void quicksort(auto left, auto right) {
  if (left != right && !std::is_sorted(left, right)) {
    // take the pivot from the mostleft element
    auto pivot = *left;
    // get the partitioning point
    auto part_it = std::partition(left, right, [&pivot](const auto& item) { return item < pivot; });
    // and call the quicksort for left and
    quicksort(left, part_it);
    // right partition recursivly.
    quicksort(part_it, right);
  }
}

In case of sorting (really) large sequences containing elements without side effects on performing the less than comparison, this algorithm can be speed up by executing one of the both partitionings in another thread.
The complex thing in this case is to avoid starting too much threads. In the following example this is solved in a naive approach by simple passing a max count of threads and alternating parallelizing.
This is not optimal due to the fact the we do not know how big each part is and if a thread may be started with a small or empty part. But its only an example, there is already a better solution at the end of this post.

# include <algorithm>
# include <thread>
void quicksort(auto left, auto right, unsigned int threads = 1) {
  if (!std::is_sorted(left, right)) {
    auto pivot = *left;
    auto part_it = std::partition(left, right, [&pivot](const auto& item) { return item < pivot; });

    auto sort_left = [&left, &part_it](int _threads) { quicksort(left, part_it, _threads); };
    auto sort_right = [&part_it, &right](int _threads) { quicksort(part_it, right, _threads); };

    if (threads) {
      // if there are threads left to start, alternate the parts and start sorting one part in a new thread
      --threads;
      if (threads % 2) {
        std::jthread thr(sort_left, threads);
        sort_right(threads);
      }
      else {
        std::jthread thr(sort_right, threads);
        sort_left(threads);
      }
    }
    else {
      // no threads left, sort both parts in the current thread
      sort_left(threads);
      sort_right(threads);
    }
  }
}

The parallel algorithm with max. 1 thread performs better at a very large number, in my case I had to use an integer vector with 20mio elements before it got faster than the sequential one.

As already written, don’t take this too serious, this can be done much better and wasn’t the goal of this post.
For example have a look on std::sort which also allows a parallel execution since C++ 17:

std::sort(std::execution::par, std::begin(vec), std::end(vec));