Modern C++ compliant insertion sort
"One specific question I have deals with the unsigned integer I am adding and subtracting from the iterators to move to the next and previous values in the container. Since there is no way to get the type of container for the provided iterators, I do not see a way to get the size_type of the assumed container to add and subtract the correct types rather than just unsigned/signed integers."

I just found std::prev and std::next defined in #include &lt;iterator&gt; which I think would handle some cases of signed/unsigned mismatch I was talking about.

For other cases where you would need to perform more complicated arithmetic, such as division or multiplication, you would use:

std::iterator_traits&lt;BdIterator&gt;::difference_type


std::distance returns std::iterator_traits&lt;BdIterator&gt;::difference_type.

std::next and std::prev take std::iterator_traits&lt;BdIterator&gt;::difference_type as parameters.
Arithmetic on bidirectional iterator may go backwards.

"The fact that I am subtracting prevents me from declaring the minimal Iterator template type as forward iterators (We are moving the iterator backwards). Is there a better way around this or should I just stick to making the minimum BiDirectionalIterators?"

I failed to realize that regardless of whether I use std::prev or not, the algorithm itself relies on moving the iterators both forwards and backwards, and therefore requires BiDirectional Iterators.

There is a more efficient solution that relies on finding a hole and bubbling up the hole to then insert the value into its sorted hole.

// Shift/bubble each element toward the front into a sorted sub-array
template&lt;typename BidirIt, typename Comparator = std::less&lt;typename std::iterator_traits&lt;BidirIt&gt;::value_type&gt;&gt;
void sort_insertion(BidirIt first, BidirIt last, Comparator cmp = Comparator())
{
    using category = typename std::iterator_traits&lt;BidirIt&gt;::iterator_category;
    static_assert(std::is_base_of&lt;std::bidirectional_iterator_tag, category&gt;::value, "This algorithm requires bidirectional iterators.");

    // 1 element containers are sorted; 2 duplicate element containers are sorted.
    if (first != last)
    {
        // Make a hole by removing the element you are checking,
        // and move elements up to that hole until you find the correct position of the element removed.
        // ++cur: Assume the first element is sorted.
        for (BidirIt cur = first; ++cur != last;)
        {
            auto val = std::move(*cur);
            BidirIt next = cur, prev = std::prev(next);
            while (cmp(val, *prev))
            {
                *next = std::move(*prev);
                next = prev;
                if (prev != first) --prev;
                else break;
            }
            // insert value in its sorted hole.
            *next = std::move(val);
        }
    }
}