Why Will Std::Sort Crash If the Comparison Function Is Not as Operator ≪

Why will std::sort crash if the comparison function is not as operator <?

std::sort requires a sorter which satisfies the strict weak ordering rule, which is explained
here

So, your comparer says that a < bwhen a == b which doesn't follow the strict weak ordering rule, it is possible that the algorithm will crash because it'll enter in an infinite loop.

std::sort - is passing a faulty comparator undefined behavior?

Warning: extreme language-lawyering follows.

The wording of the most recent draft of the standard puts it this way in [alg.sorting]p3:

For all algorithms that take Compare, there is a version that uses operator< instead. That is, comp(*i, *j) != false defaults to *i < *j != false. For algorithms other than those described in 25.4.3, comp
shall induce a strict weak ordering on the values.

By using the word "shall", the standard is implicitly stating that violating it leads to undefined behavior.

Whether this requires that the given function impose a SWO for all possible values or just for the values given to the algorithm is not clear from the standard. However, since the restriction is stated in a paragraph that is talking about those specific algorithms, it's not unreasonable to assume that it is refering to the range of values provided to the algorithm.

Otherwise, the default operator< could not impose SWO for floats, thanks to NaN.

Why does inbuilt sort function for c++ does not function when we use equals '=' sign in comparator function?

Because the ≤ relation is not a strict weak ordering.

Strict weak ordering is is defined by:

A strict weak ordering is a binary relation < on a set S that is a strict partial order (a transitive relation that is irreflexive, or equivalently,[6] that is asymmetric) in which the relation "neither a < b nor b < a" is transitive.

Note the requirement of irreflexivity.

A binary relation is called irreflexive, or anti-reflexive, if it doesn't relate any element to itself.

It is easy to show that ≤ does not have this property. Consider for example: 0 ≤ 0. Clearly, this number (and also all other integers) is related with itself, so ≤ is not irreflexive (it is reflexive) and therefore is not a strict partial order and therefore it is not a strict weak ordering.

The comparison function of std::sort is required to be a strict weak ording. Using ≤ violates this requirement, and behaviour of using it is undefined.

Crash in std::sort - sorting without strict weak ordering

I'll just go off of the comment in your code and explain what's wrong with it (if anything), and how you would fix it.

// Sort the participants so that ones with more action points (mAp) go first.

Good so far

// When there is a tie, participants with the same disposition (mDisposition) as the initiator of the battle (mBattleInitiator) go first.

What if both participants have the same disposition as the initiator? Even if you can guarantee that no 2 elements will satisfy this condition, the sort algorithm is allowed to compare an element against itself. This test would return true in that case, violating one of the conditions of a strict-weak ordering, which is that an element must compare equal to itself (i.e. compare(a,a) must always be false).

Perhaps instead you want to say that if a has the same disposition as the initiator, and b does not, then a should be considered less than b. This can be encoded as:

return dispositionOfA == mBattleInitiator && dispsitionOfB != mBattleInitiator;

So your full test would look like this:

if (a.mAp > b.mAp)
    return true;
if (a.mAp < b.mAp)
    return false;

return a.mAiComponent->mDisposition == mBattleInitiator &&
       b.mAiComponent->mDisposition != mBattleInitiator;

c++ sort will crash while stable_sort won't, but both take no effect

From the comment it seems the problem was a missing assignment of SignalDB in the assignment operator. This missing assignment would easily explain why neither sorting algorithm would actually sort the values: there is some random value there which keeps changing for the values.

Incidentally it also explains why std::sort() crashes while std::merge_sort() doesn't although there is certainly no guarantee that std::merge_sort() won't crash: the sorting criteria has to be a Strict Weak Order and the values being sorted have to be copyable. If these constraints don't hold, the behavior of either algorithm is undefined. The copyable constraint states that the copy of a value can't be distinguished from the original and can be used entirely interchangeably. If the value being compared on isn't really copied that isn't is the case.

The difference in crashing vs. non-crashing is based on how the sorting is actually implemented. Note that neither sort is guaranteed to crash as the behavior is undefined in either case. However, std::stable_sort() uses an algorithm which is more likely to just produce wrong results than to crash. To minimize the operations done in an inner loop of std::sort() a sentinel is used at the beginning of the sequence: in a strategic fashion it is made sure that a small enough element ends up in the right location of the sequence. This way the inner loop only needs to compare the values rather than also verifying if the value is still in the range: due to the sentinel a search used in the inner loop it will never try to move off the sequence. However, if that smallest element gets a more or less random value being ordered on it may turn out not to be the smallest element at all and the "sentinel" isn't really one, having the search wander off into looking at fields it isn't meant to look at.

For a more detailed explanation you might want to watch the last two videos of Stepanov's lectures on Efficient Programming with Components (although the lectures are kind of extremely slow, I think there is actually value in watching all of them). I think the specific issue is discussed in the second to last video but I don't recall exactly. The discussion is focused on the ordering not being a strict weak order but the effect is the same if the copy isn't really a copy.

Why does this simple custom-comparator of tuples crash even with strict-weak ordering?

Your cmp operator() does not have a strict weak ordering. e.g. you need to check if d1 == d2 before comparing w1 < w2 and so on. This violates the requirements of std::sort which invokes undefined behavior. This could lead to a crash.

A simple implementation that is correct would be:

bool operator() (std::tuple<int, int, int> const & t1, std::tuple<int, int, int> const & t2) {
    int d1 = std::get<0>(t1), d2 = std::get<0>(t2), w1 = std::get<1>(t1), w2 = std::get<1>(t2), b1 = std::get<2>(t1), b2 = std::get<2>(t2);
    return std::tie(d1, w1, b1) < std::tie(d2, w2, b2);     
}

As it stands, this custom comparator doesn't need to be implemented, since it's using the default ordering for std::tuple, which can be used by std::sort.

From c++17, you can clean this up a little with structured bindings:

bool operator() (std::tuple<int, int, int> const & t1, std::tuple<int, int, int> const & t2) {
    auto [d1, w1, b1] = t1;
    auto [d2, w2, b2] = t2;
    return std::tie(d1, w1, b1) < std::tie(d2, w2, b2);     
}