Sorting algorithms - Insertion sort
Important stuff:


Missing header:


The std::less&lt;&gt; is from &lt;functional&gt;.


Relying on type deduction:


Although it is generally good, the lines 

            auto&amp; i_val = *i;
            auto&amp; i_next_val = *i_next;


seem somewhat dangerous to me. For std::vector&lt;bool&gt;, for example. I think it should be at least const auto&amp;, or even better, the comparison could be called without them:

cmp(*i, *i_next);



Dangerous swap:

        auto&amp; i_val = *i;
        auto&amp; i_next_val = *i_next;
        if (cmp(i_val, i_next_val)) {
            break;
        }
        std::iter_swap(&amp;i_val, &amp;i_next_val);



The swap assumes that types didn't overload operator&amp;. It is pretty rare these days, but still exist. The swap should just be std::iter_swap(i, i_next).

Style:


Complicated inner loop:


The control flow inside of the loop is very hard to follow. This is the version in my library:

        auto j = i;
        while (std::prev(j) != first &amp;&amp; !cmp(*std::prev(j), *j))
        {
            std::iter_swap(std::prev(j), j);
            --j;
        }


The i is the iterator of the outer loop. It might not be that descriptive, but I think it is ok. The main idea here is that while loop is used and the condition is inside of the condition brackets, which closely follows plain english description of an algorithm.


Naming:


Usually range is denoted by [first, last). At least this is what I see quite frequently on cppreference. Also, the concept is called Compare, so it might be worth sticking to it, although it is somewhat confusing.

Testing:

There is std::greater template function object which could be used instead of handwritten lambda.