Сортировка вставками ( insertSort ) очень проста в реализации и быстро работает для небольших массивов.
Вот её реализация в виде двух шаблонов функций:

template <class T> inline
ArrRef<T> insertSort123 ( ArrRef<T> a )
{
    for ( nat j = 1; j < a.size(); ++j )
    {
        const T b = a[j];
        int i = j - 1;
        while ( i >= 0 && a[i] > b )
        {
            a[i+1] = a[i];
            --i;
        }
        a[i+1] = b;
    }
    return a;
}

template <class T> inline
ArrRef<T> insertSort321 ( ArrRef<T> a )
{
    for ( nat j = 1; j < a.size(); ++j )
    {
        const T b = a[j];
        int i = j - 1;
        while ( i >= 0 && a[i] < b )
        {
            a[i+1] = a[i];
            --i;
        }
        a[i+1] = b;
    }
    return a;
}

Исходники находятся в файле func1t.h.