What's wrong with qsort comparator?

Question

So I've been doing my homework on C, and there was this task: "An array of ints is given, write a function that sorts them in following way: first, the even numbers in non-decreasing order, second, the odd numbers in non-increasing". For example, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] -> [2, 4, 6, 8, 10, 9, 7, 5, 3, 1].

The task itself is about writing a comparator function for qsort correctly. I wrote the following cmp:

int
cmp(const void *elem1, const void *elem2)
{
    int p_number1 = *(int *) elem1, p_number2 = *(int *) elem2, diff_flag = 0;
    if (p_number1 > p_number2) {
        diff_flag = 1;
    } else if (p_number1 < p_number2) {
        diff_flag = -1;
    }
    if ((p_number1 & 1) == (p_number2 & 1)) { // same parity
        return diff_flag == 0 ? 0 : diff_flag ^ ((p_number1 & 1) << 31);
        /* in even case, diff_flag will be returned, otherwise,
         * number with sign that is different from diff_flag's will be returned */
    }
    return (p_number1 & 1) - (p_number2 & 1); // if first is odd, and second is even, 1 is returned, and vice versa
}

and the testing system spits out a runtime error. it does return INT_MIN and INT_MAX for less and bigger cases respectively, but doesn't that satisfy qsort's specifications? besides, it worked fine on all the arrays I was testing it with locally. Maybe anyone knows why is there a RE?

P.S. I understand I'm making it in the most non-readable way possible, but I am obliged to rely mostly on bit ops and do everything in most optimal way possible, so I apologize for complexity.

Answer 1

(p_number1 & 1) << 31 is undefined behavior (UB) when p_number1 & 1 is non-zero.

Shifting a 1 into the sign bit is UB. Even if it is unfortunately taught as some way to perform bit manipulations and/or works on OP's machine, it remains UB and should be avoided.

It is also UB when int is 16-bit as shifting the width or more is UB.

A runtime error is one form of UB.

---

Alternative

int
cmp(const void *elem1, const void *elem2)
{
    int p_number1 = *(const int *) elem1; // Better form to not cast away const
    int p_number2 = *(const int *) elem2;
    if ((p_number1 ^ p_number2) & 1)) { // never UB with 2's complement
      return (p_number1 & 1) - (p_number2 & 1); 
    }
    // Only compare values when the same "parity".
    int diff_flag = (p_number1 > p_number2) - (p_number1 < p_number2);
    if (p_number1 & 1) {
      diff_flag = -diff_flag;
    }
    return diff_flag;
}

Answer 2

I would try to aim for readable, understandable code, rather than relying on knowledge of the bit patterns of ints, and using XOR and shifts.

Something like:

int cmp(const void *elem1, const void *elem2)
{
    int number1 = *(int *) elem1;
    int number2 = *(int *) elem2;
    int odd1 = number1 & 1;
    int odd2 = number2 & 1;
    int rv;

    // Special case for equal, to simplify the ternary expressions below
    if (number1 == number2)
        return 0;

    if (odd1) {
        if (odd2)
            rv = number2 > number1 ? 1 : -1;
        else
            rv = 1;
    } else {
        if (!odd2)
            rv = number1 > number2 ? 1 : -1;
        else
            rv = -1;
    }
    return rv;
}

This will also work on different sized ints, rather than relying on 32-bit ints.

Answer 3

You should check the parity first, as in this code.

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *elem1, const void *elem2)
{
    int a = *(int *) elem1;
    int b = *(int *) elem2;
    
    // compare the parity
    int diff = (a & 1) - (b & 1);
    if(diff)
        return diff;
        
    // compare the magnitude
    if((a & 1) == 0)
        return (a > b) - (a < b);
    else 
        return (b > a) - (b < a);
}


int main(void)
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int len = sizeof arr / sizeof arr[0];
    qsort(arr, len, sizeof arr[0], cmp);
    
    for(int i=0; i<len; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

Program output

2 4 6 8 10 9 7 5 3 1