template <typename Iter>
void lin_sort(Iter begin, Iter end) {
    for (auto cur = begin; cur != end; ++cur) {
        auto key = *cur;
        auto ins = cur - 1;
        for (; begin <= ins && key < *ins; --ins)
            *(ins + 1) = *ins;    // move 1 to right until correct position's found
        *(ins + 1) = key;
    }
}

template <typename Iter>
void ins_sort(Iter begin, Iter end) {
    for (auto cur = begin; cur != end; ++cur) {
        // upper_bound is binary search for correct insertion position
        // shift everything from up to cur to the right one and insert key into right place
        std::rotate(std::upper_bound(begin, cur, *cur), cur, cur + 1);
    }
}

template <typename Iter>
void ins_sort(Iter begin, Iter end) {
    for (auto cur = begin; cur != end; ++cur) {
        auto key = *cur;
        auto ins = std::upper_bound(begin, cur, key);
        for (auto shift = cur; shift != ins; --shift) *shift = *(shift-1);
        *ins = key;
    }
}

mylibsalgo>algotest s l
after: 100000 lists with 64 elements: 1.11421e+06 us    1114.21 ms  (linear insertion sort)
mylibsalgo>algotest s i
after: 100000 lists with 64 elements: 1.62741e+06 us    1627.41 ms  (binary insertion sort)