quick_sort.cpp

namespace detail {

    template<typename It>
    It partition(It begin, It end) {
        if (begin == end) return end;
        auto pivot = *(end - 1);
        auto left = begin; // left partion past the end
        for (auto right = begin; right != end; ++right) {
            if (*right <= pivot) {
                std::iter_swap(left, right);
                ++left;
            }
        }
        return left;
    }
    
}

template<typename It>
void quick_sort(It begin, It end) {
    if (begin == end) return;
    auto pivot = detail::partition(begin, end);
    quick_sort(begin, pivot - 1);
    quick_sort(pivot, end);
}