Sorting algorithms - Insertion sort This is a follow-up question to Sorting algorithms - Bubble sort  

Again, for practice purposes only, I took on an implementation of the well known insertion sort as a method to be used similarly to std::sort.  

As expected, the code lives inside a header file called insertion_sort.h:

#pragma once

#include &lt;iterator&gt;
#include &lt;algorithm&gt;

namespace sorting_algorithms {
    template &lt;typename BidirectionalIterator,
            typename Comparator = std::less&lt;&gt;&gt;
    void insertion_sort(BidirectionalIterator begin, BidirectionalIterator end,
            Comparator cmp = {}) {

        if (std::distance(begin, end) &lt; 2) {
            return;
        }

        for (auto current_element = std::next(begin); current_element != end;
                ++current_element) {
            for (auto i = std::prev(current_element), i_next = current_element;
                    i_next != begin; --i, --i_next) {
                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);
            }
        }
    }
}


I tried to follow most hints and suggestions I received for my previous question about bubble sort. I am aware of the fact that the algorithm can also be implemented in a way that only requires forward iterators, but I decided to require bidirectional iterators here for ease of implementation.  

Again, I also provide you a main file for simple compilation and testing purposes:

#include &lt;random&gt;
#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;iomanip&gt;
#include &lt;chrono&gt;
#include &lt;algorithm&gt;

#include "insertion_sort.h"

int main() {
    unsigned seed =
        std::chrono::system_clock::now().time_since_epoch().count();
    std::default_random_engine engine(seed);
    std::uniform_int_distribution&lt;unsigned&gt; distribution(0, 10000);

    std::vector&lt;unsigned&gt; vec;
    for (std::size_t i = 0; i &lt; 100; ++i) {
        unsigned num = distribution(engine) + 1;
        std::cout &lt;&lt; num  &lt;&lt; ' ';
        vec.push_back(num);
    }
    std::cout &lt;&lt; "\n\n";

    sorting_algorithms::insertion_sort(vec.begin(), vec.end());

    for (const auto&amp; e : vec) {
        std::cout &lt;&lt; e &lt;&lt; ' ';
    }

    std::cout &lt;&lt; std::boolalpha;
    std::cout &lt;&lt; "\nSorted? " &lt;&lt; std::is_sorted(vec.begin(), vec.end())
        &lt;&lt; "\n\n";

    sorting_algorithms::insertion_sort(vec.begin(), vec.end(),
            [] (const auto&amp; v0, const auto&amp; v1) {
                return v0 &gt; v1;
            });

    for (unsigned e : vec) {
        std::cout &lt;&lt; e &lt;&lt; ' ';
    }
    std::cout &lt;&lt; "\nSorted (in reverse order)? "
        &lt;&lt; std::is_sorted(vec.begin(), vec.end(),
            [] (const auto&amp; v0, const auto&amp; v1) {
                return v0 &gt; v1;
            }) &lt;&lt; '\n';
}
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.