c++algorithmsortingclang++insertion-sort

Why does std::is_sorted() change between calls with clang

I have some code which is showing odd behavior when std::is_sorted() is called twice in a row; the result changes! The fist call returns false and the second call returns true. This happens with the following

while compiling with -O2 -std=c++20. I also tested with c++11 and c++17. The code below uses a sort algorithm to sort a std::array<> then check to see that it is std::is_sorted(). This is actually a minimum reproduction of a test case in another code base. I believe the algorithm is correct. If I print the contents of the array before calling std::is_sorted() the contents are printed in the expected order and both calls to std::is_sorted() return true. I cannot reproduce this on lower optimization levels and GNU g++ performed as expected.

#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>

template<class T>
void insertion_sort(T begin, T end)
{
    T current = begin;
    ++current;
    while(current < end) {
        auto key = *current;
        auto j = current - 1;
        while(j >= begin && *j > key) {
            *(j+1) = *j;
            --j;
        }
        *(j+1) = key;
        current++;
    }
}

int main(int argc, char* argv[])
{
    std::array<int, 6> a{5, 2, 4, 6, 1, 3};
    insertion_sort(a.begin(), a.end());
    std::cout << std::is_sorted(a.begin(), a.end()) << std::endl;
    std::cout << std::is_sorted(a.begin(), a.end()) << std::endl;
    return 0;
}
Solution

  • It seems the problem is that your code has undefined behavior. In this while loop

            while(j >= begin && *j > key) {
            *(j+1) = *j;
            --j;
        }

    the iterator j is decremented when it is equal to begin.

    Also within the function you need to check whether begin is not equal to end before this increment ++current;.

    If your compiler supports the C++20 Standard then the function can look for example the following way.

    #include <iostream>
#include <array>
#include <iterator>
#include <algorithm>

template<class BidirectionalIterator>
void insertion_sort( BidirectionalIterator first, BidirectionalIterator last )
{
    if ( first != last )
    {
        for ( auto current = first; ++current != last; )
        {
            auto prev = current;

            while ( prev != first && *current < *std::prev( prev ) ) --prev;

            if ( prev != current )
            {
                auto key = *current;
                std::shift_right( prev, std::next( current ), 1 );
                *prev = key;
            }
        }
    }
}

int main() 
{
    std::array<int, 6> a{5, 2, 4, 6, 1, 3};

    insertion_sort(a.begin(), a.end());

    for ( const auto &item : a ) std::cout << item << ' ';
    std::cout << '\n';

    std::cout << std::boolalpha;
    std::cout << std::is_sorted(a.begin(), a.end()) << std::endl;
    std::cout << std::is_sorted(a.begin(), a.end()) << std::endl;        
}

    The program output is

        1 2 3 4 5 6 
    true
    true

    Or the function template can have the following header

    template<std::bidirectional_iterator It>
void insertion_sort( It first, It last )