Modern C++ compliant insertion sort

Question

This is a kind of follow up to my previous sort implementation question with specific questions to insertion sort, and Modern C++ idioms. Anybody seeing this post can see how I got to this modern equivalent of a typical C-style sort you can find everywhere on the web by visiting my prior sorting review.

I am writing, as review for an interview, Modern C++ compliant versions of sorting algorithms I previously have seen. This post is about insertion sort, and insertion sort only.

// Shift/bubble each element toward the front into a sorted sub-array
template<typename BdIterator, typename Comparator = std::less<typename std::iterator_traits<BdIterator>::value_type>>
void sort_insertion(BdIterator beg, BdIterator end, Comparator cmp = Comparator())
{
    BdIterator front, cur, prev;
    // Assume the first element is sorted.
    for (front = beg + 1u; front != end; ++front)
    {
        cur = front;
        prev = cur - 1u;
        // Bubble the "next" element towards the front by swapping it with its 
        // "prev" neighbor until it is in its sorted position.
        while (cur != beg && cmp(*cur, *prev))
            std::iter_swap(cur--, prev--);
    }
}

As before, I am looking for any performance optimizations I may have missed in the algorithm itself, as well as Modern C++ constructs I may not be abiding by for this example.

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.

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?

Answer 1

"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 <iterator> 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<BdIterator>::difference_type

std::distance returns std::iterator_traits<BdIterator>::difference_type.

std::next and std::prev take std::iterator_traits<BdIterator>::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<typename BidirIt, typename Comparator = std::less<typename std::iterator_traits<BidirIt>::value_type>>
void sort_insertion(BidirIt first, BidirIt last, Comparator cmp = Comparator())
{
    using category = typename std::iterator_traits<BidirIt>::iterator_category;
    static_assert(std::is_base_of<std::bidirectional_iterator_tag, category>::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);
        }
    }
}

Answer 2

Focus on using <algorithm> as building blocks for larger functions. In the case of insertion sort with bidirectional iterators, you could separate the logic of finding the insertion point from the shifting.

template <class BidirIt, class Compare = std::less<>>
void insertion_sort(BidirIt first, BidirIt last, Compare cmp = Compare{}) {
  if (first == last || std::next(first) == last) {
    return;
  }

  using RevIt = std::reverse_iterator<BidirIt>;
  for (auto curr = std::next(first); curr != last; ++curr) {
    // Reverse Linear Search the insertion point
    const auto insertion =
        std::find_if_not(RevIt(curr), RevIt(first), [=](const auto& elem) {
          return cmp(*curr, elem);
        }).base();

    auto elem = std::move(*curr);
    std::move_backward(insertion, curr, std::next(curr));
    *insertion = std::move(elem);
  }
}