C++ quicksort with iterators

quicksort.cpp

#include <algorithm>
#include <iostream>
#include <list>

template<typename Iter>
void print(const Iter& beg, const Iter& end)
{
    std::for_each(beg, end, [](auto& i) { std::cout << i << " "; });
    std::cout << std::endl;
}

template<typename Iter>
Iter part(Iter beg, Iter end, const typename Iter::value_type& pivot)
{
    Iter head = beg;
    Iter tail = std::prev(end);
    while (head != tail) {
        while (*head < pivot) {
            if (++head == tail) {
                return head;
            }
        }
        while (*tail >= pivot) {
            if (--tail == head) {
                return head;
            }
        }
        std::cout << "swap  " << *head << " ↔ " << *tail << std::endl;
        std::iter_swap(head, tail);
        std::cout << " ⇒    "; print(beg, end);
        if (++head == tail--) {
            return head;
        }
    }
    return head;
}

template<typename Iter>
void quick_sort(Iter beg, Iter end)
{
    std::cout << "sort  "; print(beg, end);

    if (beg == end) {
        return;
    }

    auto pivot = *beg;
    Iter split = part(beg, end, pivot);

    // sort left
    quick_sort(beg, split);
    // sort right
    Iter new_middle = beg;
    quick_sort(++new_middle, end);
}

int main(int argc, const char* argv[])
{
    std::list<int> l = { 3, 2, 1, 5, 2, 12, 4356, 1, 5, 12 };
    quick_sort(l.begin(), l.end());
    std::cout << "done  "; print(l.begin(), l.end());
    return 0;
}

Sure! Feel free to use it!

Also you can optimize recursion count like this: https://rextester.com/AEB21840

Hi, I tried your impl with the following and it did not work:
(A) 1 12 5 26 7 14 3 7 2; it produced: 1 2 3 7 5 7 12 14 26
(B) 3 42 1 5 32 37 4356 41 135 92; it produced: 1 5 3 32 37 41 42 92 135 4356
(C) 3 2 1 5 2 12 4356 1 5 12, with mid point pivot auto pivot = beg; std::advance(pivot, std::distance(beg, end)/2);; it produced: 3 1 1 2 2 5 5 12 12 4356
(D) 3 42 1 5 32 37 4356 41 135 92, with mid point pivot auto pivot = beg; std::advance(pivot, std::distance(beg, end)/2);; it produced: 3 1 5 32 37 41 42 92 135 4356
(E) Also, due to the weak/strong asymmetry in the comparisons done in part , it can not handle std::greater ordering.
(F) Finally, this is inefficient as it ends up making several redundant comparisons:

Iter new_middle = beg;
quick_sort(++new_middle, end);

This is what I came up with and it seems to work:

template<typename It, template<typename> class Cmp = std::less>
void mysort(It beg, It end) {
    RandomIt head = beg, bend = std::prev(end), tail = bend, pivot = beg;
    std::advance(pivot, std::distance(head, tail)/2); //Comment out if it is preferred to have the pivot at 'beg'
    using val_type = typename std::iterator_traits<It>::value_type;
    val_type pivot_val = *pivot;

    //std::cout << "sort with pivot [" << pivot_val << "]:         "; print(beg, end);
    while (head <= tail) { 
        while (Cmp<val_type>()(*head, pivot_val)) ++head;
        while (Cmp<val_type>()(pivot_val, *tail)) --tail;
        if (head <= tail) {
            std::cout << "swap(h,t)  " << *head << " ↔ " << *tail << std::endl;
            std::iter_swap(head, tail);
            ++head;
            --tail;
        }
    };
    //std::cout << "post partition - head[" << *head << "], tail[" << *tail << "]:  "; print(beg, end);

    if (beg < tail) {
        mysort<It, Cmp>(beg, std::next(tail));
    }
    if (head < bend) { //Use 'before end' iterator to avoid unnecessary iteration with just the last element
        mysort<It, Cmp>(head, end);
    }
}