Общий алгоритм сортировки вставкой не перемещает первый объект в списке

Question

Мне нужно создать общий алгоритм сортировки вставками, используя семантику перемещения. У меня он работает для целых списков различных типов объектов, за исключением самого первого объекта в списке.

template<typename Iter, typename Comparator>
void insertionSort(const Iter& begin, const Iter& end, Comparator compareFn)
{
    for (auto i = begin + 1; i < end; i++)
    {
        auto currentthing = std::move(*i);
        auto j = std::move(i - 1);

        while (j >= begin and compareFn(*j, currentthing))
        {
            *(j + 1) = std::move(*j);
            if (j == begin)
                break;
            j--;
        }
        *(j + 1) = std::move(currentthing);
    }    
}

Где сравнивается список строк из моей основной функции:

int main()
{
    vector<int> numbers = { 0, 1, 8, 4, 2, 9, 5, 3, 6, 7, 10 };
    insertionSort(numbers.begin(), numbers.end(), std::less<int>());

    cout << "Sorted: " << numbers << "\n";

    vector<string> names = { "p", "a", "b", "d", "c", "f", "e" };
    insertionSort(names.begin(), names.end(), std::greater<string>());

    cout << "Sorted: " << names << "\n";

    return 0;
}

Выводит следующее

Sorted: [ 0 10 9 8 7 6 5 4 3 2 1 ]
Sorted: [  a b c d e f ]

Answer 1

while l oop должно прерваться, когда j равно i, а не когда j равно begin. Итак, следующее:

if (j == begin)
    break;

должно быть:

if (j == i)
    break;