quick_sort.h

#ifndef ALGOPLUS_QUICK_SORT_H
#define ALGOPLUS_QUICK_SORT_H
 
#include <algorithm> // For std::partition and std::swap
#include <iterator>  // For std::iterator_traits

template <typename Iter> Iter median_of_three(Iter a, Iter b, Iter c) {
    if (*a < *b) {
        if (*b < *c)
            return b;
        else if (*a < *c)
            return c;
        else
            return a;
    } else {
        if (*a < *c)
            return a;
        else if (*b < *c)
            return c;
        else
            return b;
    }
}

template <typename Iter> void quick_sort(Iter begin, Iter end) {
    auto distance = std::distance(begin, end);
    if (distance <= 1) {
        return;
    }
 
    // choose the pivot as median of first, middle and last element
    Iter mid = begin + distance / 2;
    Iter pivot_pos = median_of_three(begin, mid, end - 1);
    auto pivot = *pivot_pos;
 
    // swap pivot to start
    std::swap(*begin, *pivot_pos);
 
    Iter middle1 =
        std::partition(begin + 1, end, [pivot](const auto& elem) { return elem < pivot; });
 
    Iter middle2 =
        std::partition(middle1, end, [pivot](const auto& elem) { return !(pivot < elem); });
 
    // swap pivot to its final place
    std::swap(*begin, *(middle1 - 1));
 
    // recursively apply quick_sort to partitions
    quick_sort(begin, middle1 - 1);
    quick_sort(middle2, end);
}
 
#endif // QUICK_SORT_H