Recently, I was solving this problem : 2219C - Coloring a Red Black Tree While writing the solution, I encountered a runtime error with my submission 377542151.

After trying to find out the bug for 30 mins I finally got the error. I have written a decent amount of C++ but this is the first time I have encountered a runtime error caused by std::sort

The exact problem lies in this part of the code :

    sort (tree[u].adj.begin(), tree[u].adj.end(), [&tree](int a, int b) {
        return ((tree[a].exp0 - tree[a].exp1) <= (tree[b].exp0 - tree[b].exp1));
    });

while it looks pretty normal the bug is caused by the use of <= in std::sort while investigating I found out that there are some properties that must be satisfied while using std::sort

• The comparator must obey strict weak ordering i.e compare(A, A) must return false
• If compare(A, B) returns true, compare(B, A) must return false.
• If compare(A, B) returns true, compare(B, C) returns true, then compare(A, C) must also be true.

While the last point seems obvious, the other 2 are important findings.

How does it cause the segfault?

Quicksort partitions the array using two pointers moving toward each other. The pointers stop moving when they hit an element equal to the pivot, allowing the algorithm to swap them. This happens because a valid < comparator returns false when comparing two equal elements, acting as a brake.

By using <=, my comparator returned true when it hit elements equal to the pivot. The pointer never hit the brake.

Boom—Segmentation Fault.

Don't downvote bcz it's a common thing to know as I DID NOT KNOW ABOUT IT ! ( T_T )