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

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.

Solution

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.