Double insertion sort implementation

double_insertion_sort.h++

#include <algorithm>
#include <iterator>
#include <utility>

template<typename RandomAccessIterator, typename Compare>
auto double_insertion_sort(RandomAccessIterator first, RandomAccessIterator last, Compare compare)
    -> void
{
    auto size = last - first;
    if (size < 2) return;

    RandomAccessIterator mid_left, mid_right;
    if (size % 2 == 1) {
        // Odd number of elements
        mid_left = first + size / 2 - 1;
        mid_right = first + size / 2 + 1;
    } else {
        // Even number of elements
        mid_left = first + size / 2 - 1;
        mid_right = first + size / 2;
        if (compare(*mid_right, *mid_left)) {
            std::iter_swap(mid_right, mid_left);
        }
        ++mid_right;
        if (mid_right == last) return;
        --mid_left;
    }

    while (true) {
        // Switch the bounds if needed, this notably ensures
        // that both searches will be guarded
        if (compare(*mid_right, *mid_left)) {
            std::iter_swap(mid_right, mid_left);
        }

        // Insert from the left
        {
            auto sift = mid_left;
            auto sift_1 = std::next(sift);
            if (compare(*sift_1, *sift)) {
                auto tmp = std::move(*sift);
                do {
                    *sift = std::move(*sift_1);
                    ++sift;
                } while (compare(*++sift_1, tmp));
                *sift = std::move(tmp);
            }
        }

        // Insert from the right
        {
            auto sift = mid_right;
            auto sift_1 = std::prev(sift);
            if (compare(*sift, *sift_1)) {
                auto tmp = std::move(*sift);
                do {
                    *sift = std::move(*sift_1);
                    --sift;
                } while (compare(tmp, *--sift_1));
                *sift = std::move(tmp);
            }
        }

        // Increment
        ++mid_right;
        if (mid_right == last) return;
        --mid_left;
    }
}