Comparators & Stability

std::sort(v.begin(), v.end(), comp) runs an O(n log n) algorithm (introsort), and the only thing it knows about your data is your function comp(a, b), which answers: should a come before b?

That means you can sort by any rule:

• descending: return a > b;
• by a field: return a.score > b.score;
• by several keys: compare the first key; only if equal, compare the next

In other languages it looks different but works the same: Python sorted(v, key=lambda p: (-p.score, p.name)), Java Comparator.comparing(...). A key function returning a tuple is often the easiest way to get orders on several keys right.

The comparator must behave like a strict "less than" (a strict weak ordering):

• comp(a, a) is false: nothing comes before itself
• if comp(a, b) is true, comp(b, a) must be false
• it must be transitive: a before b and b before c means a before c

The classic bug is writing <= instead of <. Then comp(x, x) is true, the algorithm's assumptions break, and std::sort can return garbage or even read past the end of the array and crash. Another trap: comparing doubles that may be NaN, or a "random" comparator to shuffle.

Also keep the comparator cheap: it runs about n log n times. Precompute values like ratios once instead of recomputing them in every call.