Sorting algorithm works for C-array but not works for std::span

Question

This problem happens when I am working on a insertion_sort algorithm. I tried to implement a version for C++20's std::span but it throws a "std::span index out of range" So I turned it to "C-array" the same code works fine. I don't know where is the problem. P.S My platform is windows10 and I'm using VisualStudio2022

This is the std::span version.

template <typename Ty>
void insertion_sort(std::span<Ty> arr) {
    long long size = arr.size();
    // From the 2nd element to the nth element
    for (long long i = 1; i < size; ++i) {
        Ty key = arr[i];
        long long j = i - 1;
        // Until the first element.
        for (; arr[j] > key && j >= 0; --j)
            arr[j + 1] = arr[j];
        // Place key into the right position.
        arr[j + 1] = key;
    }
}

However if I change std::span to C-array, like below, it works fine.

template <typename Ty>
void insertion_sort(Ty* arr, std::size_t size) {
    // From the 2nd element to the nth element
    for (long long i = 1; i < size; ++i) {
        Ty key = arr[i];
        long long j = i - 1;
        // Until the first element.
        for (; arr[j] > key && j >= 0; --j)
            arr[j + 1] = arr[j];
        // Place key into the right position.
        arr[j + 1] = key;
    }
}

I'll be glad if someone can help me fix this problem!

Answer 1

The condition in the for loop

    for (; arr[j] > key && j >= 0; --j)
        arr[j + 1] = arr[j];

is wrong. You need to exchange the operands of the logical AND operator

    for (; j >= 0 && arr[j] > key; --j)
        arr[j + 1] = arr[j];

Otherwise the index of the expression arr[j] can be equal to -1.