How to perform stable sort in C++ when using a custom comparator?

Question

I am trying to write a custom comparator in C++ to sort a vector. For the sake of simplicity, I will say my sorting criteria is that all even values should come before all odd values and I am trying to write a custom comparator for this. But I need to make sure that the relative order of all even elements and all odd elements is preserved.

I am using this code:

bool mysort(int arg1,int arg2){
    return arg1%2==0;
}

int main(){
    vector<int> v({1,3,2,4,5,7,9,6,8,11,10,12});
    stable_sort(v.begin(),v.end(),mysort);
    for(int i=0;i<v.size();i++){
        cout<<v[i]<<" ";
    }
    return 0;
}

Based on what I understand, when mysort() returns true, it means first argument (arg1) is allowed to be before the second argument (arg2). That why I have used return arg1%2==0; in the comparator.

But the output I get is 12 10 8 6 4 2 1 3 5 7 9 11. Which means, relative order of even elements is reversed. While, relative order of odd elements is preserved.

Instead, if I use return i%2==0 && j%2!=0; in mysort() comparator, the output I get is 2 4 6 8 10 12 1 3 5 7 9 11. Which preserves the relative order of all odd and even elements.

Why is this behavior? And what is the best way to write a custom comparator with preserving relative order of similar elements? Thank you in advance.

Answer 1

The comparator for sort and stable_sort must induce a strict weak order. Your comparator does not satisfy this condition.

One of the properties of a strict weak order is that for any permitted values of i and j, at most one of mysort(i,j) and mysort(j,i) can return true. Your comparator returns true for both cases when, e.g., i=2 and j=4.

To fix that, you must modify your comparator. When is arg1 "less" than arg2? There is only one case: When arg1 is even and arg2 is odd. Hence, a usable definition would be:

bool mysort(int arg1,int arg2){
    return arg1 % 2 == 0 && arg2 % 2 != 0;
}

BTW, when you define a comparator, you have at no time to think about in which order the algorithm will pass the parameters. All the (earlier, later) discussions are irrelevant. The algorithm will pass parameters in which ever order it likes. There are no guarantees.

Answer 2

As I'm sure you know, stable_sort preserves the order of elements which compare equal. To do this, both mysort (i, j) and mysort (j, i) must return false when i and j compare equal. (It must also return true when i < j of course.)

It therefore follows that you must test both arg1 % 2 and arg2 % 2 in mysort to fulfill this contract, and return arg1 % 2 == 0 && arg2 % 2 != 0; does precisely what you want: it will return false when both arg1 % 2 and arg2 % 2 compare equal no matter what order the parameters are passed to it.

Answer 3

STL uses a less than compare, that means std::stable_sort() is going to pass the parameters in reverse order, it will call mysort(later_object, earlier object), so the return value is true if later_object < earlier_object (copy later_object to merged output), and false if later_object >= earlier_object (copy earlier_object to merged output).