Optimize sorting matrix entries by row and column
Option 2: Compare full linear index
  #define COMPARE(ia,ja,ib,jb) (ia*N + ja &lt; ib*N + jb ? -1 : ia*N + ja &gt; ib*N + jb)


Instead of N, use the minimal power of 2 that is not less than N. For example, if N = 10000, use $2^{14}=16348$. So we can have #define COMPARE(ia,ja,ib,jb) ((ia &lt;&lt; 14) + ja &lt; (ib &lt;&lt; 14) + jb ? -1 : (ia &lt;&lt; 14) + ja &gt; (ib &lt;&lt; 14) + jb).

Instead of using #define, we can use a function to make sure that long expression is computed only once. forceinline is defined to be the cross-platform forceinline modifier.

#define TWO_EXPONENT 14
forceinline int compare(int ia, int ja, int ib, int jb) {
    int t1 = ((ia - ib) &lt;&lt; TWO_EXPONENT) + (ja - jb);
    return (t1 &gt; 0) - (t1 &lt; 0);  //branchless computation
}


You have specified that you need to return 3 values, 1, 0, and -1. That sounds more than enough. You may want to double check if it is enough to use 1 for the case of "not smaller than". That is enough, for example, when we just want to sort an array of numbers.

Just in case you have not noticed, there are a wealth of information on how to store sparse matrix, Google search or Wikipedia entry.