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

Question

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

Apple clang version 15.0.0 (clang-1500.3.9.4)
Ubuntu clang version 15.0.7
Ubuntu clang version 18.1.3 (1ubuntu1)

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;
}

Do note whenever you see the same operation produce 2 different results back to back, it is a clear indicator that there is undefined behavior somewhere in your code. — NathanOliver
– NathanOliver, Commented Apr 12 at 20:20
I believe the algorithm is correct. -- You could have replaced insertion_sort with std::sort to see that the code is wrong, as std::sort would not have exhibited this behavior. Also, what you wrote is not an algorithm, it is code that is supposed to implement the insertion sort algorithm. Algorithms are never wrong, code that attempts to implement the algorithm can be wrong. Also you could test the insertion sort code found here. — PaulMcKenzie
– PaulMcKenzie, Commented Apr 12 at 20:59

Vlad from Moscow · Accepted Answer · 2025-04-12 21:28:54Z

11

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 )

edited Apr 12 at 21:28

answered Apr 12 at 20:17

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

PaulMcKenzie Apr 13 at 15:46

You could also add an optional compare function.

Michael Conlen Apr 17 at 16:14

The solution I used was to convert to reverse iterators so that when I'm going backwards through the container I can use rend().

Collectives™ on Stack Overflow

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

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related