insert.cpp

#include <vector>
#include <deque>
#include <list>

#if __cplusplus >= 201103L
#include <forward_list>
#endif

#include <iostream>
#include <iterator>
#include "insert.hpp"

template <class T>
void test()
{
    static const int array[] = {9, 6, 3, 5, 7, 1, 4, 2, 0, 8};
    T v(array, array + (sizeof(array) / sizeof(array[0])));
    std::cout << __PRETTY_FUNCTION__ << std::endl;
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
    insertion_sort(v.begin(), v.end());
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
}

int main()
{
    test< std::vector      <int> >();
    test< std::deque       <int> >();
    test< std::list        <int> >();

#if __cplusplus >= 201103L
    test< std::forward_list<int> >();
#endif

    return 0;
}

insert.hpp

#pragma once
#include <iterator>
#include <functional>
#include <iostream>

template <typename Iterator, typename Compare>
void __insertion_sort(Iterator begin, Iterator end, Compare compare, std::forward_iterator_tag) {
    std::cout << __PRETTY_FUNCTION__ << std::endl;
    typename std::iterator_traits<Iterator>::difference_type size = std::distance(begin, end);
    while (size > 1) {
        --size;
        Iterator curr = begin;
        std::advance(curr, size - 1);
        Iterator next = curr;
        for (++next; next != end && compare(*next, *curr); ++curr, ++next) {
            std::iter_swap(curr, next);
        }
    }
}

template <typename Iterator, typename Compare>
void __insertion_sort(Iterator begin, Iterator end, Compare compare, std::bidirectional_iterator_tag) {
    std::cout << __PRETTY_FUNCTION__ << std::endl;
    if (std::distance(begin, end) <= 1) {
        return;
    }
    Iterator sep = begin;
    for (std::advance(sep, 1); sep != end; ++sep) {
        Iterator curr = sep;
        Iterator prev = sep;
        for (--prev; curr != begin && compare(*curr, *prev); --curr, --prev) {
            std::iter_swap(curr, prev);
        }
    }
}

template <typename Iterator, typename Compare>
inline void __insertion_sort(Iterator begin, Iterator end, Compare compare, std::random_access_iterator_tag) {
    __insertion_sort(begin, end, compare, std::bidirectional_iterator_tag());
}

template <typename Iterator>
inline void insertion_sort(Iterator begin, Iterator end) {
    __insertion_sort(begin, end, std::less<typename std::iterator_traits<Iterator>::value_type>(), typename std::iterator_traits<Iterator>::iterator_category());
}

template <typename Iterator, typename Compare>
inline void insertion_sort(Iterator begin, Iterator end, Compare compare) {
    __insertion_sort(begin, end, compare, typename std::iterator_traits<Iterator>::iterator_category());
}