insertion sortをジェネリックに実装してみた

namespace hito {

namespace detail {

template < typename Iterator >
void rotate( Iterator first, Iterator last )
{
    using namespace std ;

    for ( Iterator i = first ; i != last ; ++i )
    {
        swap( *first, *i ) ;
    }
}

}

template < typename Iterator, typename Compare >
void insertion_sort(
    Iterator first,
    Iterator last,
    Compare comp  )
{
    typedef typename std::iterator_traits<Iterator>::value_type value_type ;

    Iterator i = first ;
    for ( ++i ; i != last ; ++i )
    {
        Iterator iter =
            std::find_if( first, i,
                [&](value_type const & value){ return comp( *i, value ) ; }
            ) ;

        if ( iter != i )
        {
            Iterator last = i ;
            ++last ;
            detail::rotate( iter, last ) ;
        }
    }
}

}

やりすぎたかもしれない。

調べたら、広く知られているinsertion sortのコードは駄目すぎる - やねうらお－よっちゃんイカを食べながら年収1億円稼げる(かも知れない)仕事術よりちょっぴり遅かった。

ただ、insertion sortは、ほとんどソートされた配列に提供するのが筋である。だから、逆から追っていくのが普通の実装だ。bidirectionalにしていいなら、もうすこし早くなるのかも。

追記：std::move()のイテレーターは、オーバーラップできないので、自前で書いた。