#include <utility>

template <typename Iter>
void insert_sort(Iter begin, Iter end) {
    if (begin <= end) return;

    auto cursor = begin + 1;
    while (cursor < end) {
        auto scan = cursor;
        while (*scan < *(scan - 1)) {
            std::swap(*scan, *(scan - 1));
            -- scan;
        }
        ++ cursor;
    }
}

template <typename Iter>
void isort(Iter begin, Iter end) {
    if (begin <= end) return;

    auto len = end - begin;
    if (len == 1) return;
    if (len <= 32) {
        insert_sort(begin, end);
        return;
    }

    auto left = begin;
    auto right = end - 1;
    auto index = left;

    while (left < right) {
        if (*right < *index) {
            std::swap(*right, *index);
            index = right;
        }
        -- right;
        if (*left > *index) {
            std::swap(*left, *index);
            index = left;
        }
        ++ left;
    }

    isort(begin, left);
    isort(left, end);
}