How to alternate sort between even and odds ascendingly in C++?

Question

I have an array of equal even and odd integers. I want to sort the array such that array would be in that pattern: even1, odd1, even2, odd2, even3, odd3,.. and so on where even1 <= even2 <= even3 and odd1 <= odd2 <= odd3.

For instance if array is [1, 2, 3, 4, 5, 6]. Sorted array would be [2, 1, 4, 3, 6, 5].

I want to do that using std::sort compare function. But unfortunately I couldn't. I believe it's impossible to do that.

bool cmp(int lhs, int rhs) {
    // couldn't write anything
}

Answer 1

If you create a compare function that puts all odd numbers before even and simply compares within those groups, you can in one sort have all odds sorted followed by all evens sorted.

You'd then need to swap them correctly.

Something like this

bool cmp(int lhs, int rhs) {
    if ((lhs ^ rhs) & 1) // different oddness
        return lhs & 1;  // place odds first
    return lhs < rhs;
}