Original quicksort.h  #include <algorithm>namespace quicksort {template <typename iterator, typename value_type>struct traits {    static iterator choose_pivot (iterator first, iterator last) {        return first + (last - first) / 2 ;    }    static iterator partition (iterator first, iterator last, iterator pivot) {        --last ;        traits::swap (*pivot, *last) ;        pivot = last ;        while (true) {            while (*first < *pivot) {                ++first ;            }            --last ;            while (*pivot < *last) {                --last ;            }            if (first >= last) {                traits::swap (*pivot, *first) ;                return first ;            }            traits::swap (*first, *last) ;            ++first ;        }    }    static void swap (value_type &lhs, value_type &rhs) {        std::swap (lhs, rhs) ;    }};template <typename iterator, typename value_type>void sort (iterator first, iterator last){    if (first >= last) {        return ;    }    auto pivot = traits<iterator, value_type>::choose_pivot (first, last) ;    auto next_pivot = traits<iterator, value_type>::partition (first, last, pivot) ;    sort <iterator, value_type> (first, next_pivot) ;    sort <iterator, value_type> (next_pivot + 1, last) ;}} // end of namespace quicksortDriver.cpp  #include quicksort.h#include <vector>#include <string>#include <iostream>template <typename DataType, template <typename ...> class Container>void print_container (const Container <DataType> &container){    for (const DataType &d : container) {        std::cout << d <<   ;    }    std::cout << std::endl ;}template <typename DataType, template <typename ...> class Container>void run_test (const std::string &name, Container <DataType> &&container){    std::cout << name << :\n ;    print_container <DataType, Container> (container) ;    quicksort::sort <typename Container<DataType>::iterator, DataType> (std::begin (container), std::end (container)) ;    std::cout << name <<  quicksorted:\n ;    print_container <DataType, Container> (container) ;}int main (void){    run_test <int, std::vector> (vec1, std::vector <int> {5, 4, 3, 1, 2}) ;    run_test <int, std::vector> (vec2, std::vector <int> {5, 4, 10, 7, 6, 11, 14, 17, 12, 3, 1, 2}) ;    return 0 ;}Updated quicksort.h  #include <algorithm>#include <iterator>namespace quicksort {namespace detail {struct first_pivot_selector{    template <typename Iterator>    static Iterator choose_pivot (Iterator first, Iterator last) {        return first ;    }};struct middle_pivot_selector{    template <typename Iterator>    static Iterator choose_pivot (Iterator first, Iterator last) {        auto distance = std::distance (first, last) / 2 ;        std::advance (first, distance) ;        return first ;    }};struct last_pivot_selector{    template <typename Iterator>    static Iterator choose_pivot (Iterator first, Iterator last) {        return last ;    }};// Kept for debuggingstruct my_pivot_selector{    template <typename Iterator>    static Iterator choose_pivot (Iterator first, Iterator last) {        return first + (last - first) / 2 ;    }};struct std_partition {    template <typename Iterator>    static Iterator partition (Iterator first, Iterator last, Iterator pivot)    {        using value_type = typename std::iterator_traits<Iterator>::value_type ;        return std::stable_partition (first, last, [=] (const value_type &v) {            return v < *pivot ;        }) ;    }};// Kept for debuggingstruct my_partition{    template <typename Iterator>    static Iterator partition (Iterator first, Iterator last, Iterator pivot)    {        --last ;        std::swap (*pivot, *last) ;        pivot = last ;        while (true) {            while (*first < *pivot) {                ++first ;            }            --last ;            while (*pivot < *last) {                --last ;            }            if (first >= last) {                std::swap (*pivot, *first) ;                return first ;            }            std::swap (*first, *last) ;            ++first ;        }    }};} // end of namespace detailtemplate <typename Iterator, typename Pivot = detail::middle_pivot_selector, typename Partition = detail::my_partition>void sort (Iterator first, Iterator last){    if (first >= last) {        return ;    }    auto pivot = Pivot::choose_pivot (first, last) ;    auto next_pivot = Partition::partition (first, last, pivot) ;     sort <Iterator, Pivot, Partition> (first, next_pivot) ;    sort <Iterator, Pivot, Partition> (next_pivot + 1, last) ;}} // end of namespace quicksortDriver.cpp  #include quicksort.h#include <vector>#include <string>#include <iostream>template <typename Container>void print_container (const Container &container){    for (const typename Container::value_type &v : container) {        std::cout << v <<   ;    }    std::cout << std::endl ;}template <typename Container>void run_test (const std::string &name, Container container){    std::cout << name << :\n ;    print_container (container) ;    quicksort::sort (std::begin (container), std::end (container)) ;    std::cout << name <<  quicksorted:\n ;    print_container (container) ;}int main (void){    run_test (vec1, std::vector <int> {5, 4, 3, 1, 2}) ;    run_test (vec2, std::vector <int> {5, 4, 10, 7, 6, 11, 14, 17, 12, 3, 1, 2}) ;    return 0 ;}ProblemBased on these changes, std_partition::partition produces incorrect results.  I found some code that follows a similar strategy on wikibooks. T middle = partition (begin, end, bind2nd(                    less<typename iterator_traits<T>::value_type>(), *begin));sort (begin, middle);T new_middle = begin;sort (++new_middle, end);The problem is that this would break my current algorithm. I guess I could do a partial-specialization.
Templated Quicksort
c++;c++11;template;quick sort