Radix sort is deceiving
Well, I guarantee that qsort doesn't start with a heap allocation. Benchmark several different sizes of array and graph the results, to see where the lines hit the Y-axis: how much of your benchmark is just measuring the speed of malloc?



size_t count[2] = {0};


Depending on the smartness of your compiler, an array that doesn't have to be an array might be a big performance hit. Arrays are often stored in memory, on the stack, as opposed to scalar variables which can be stored in registers without any real cleverness on the compiler's part. Plus, in this case, your code seems to be needlessly convoluted by the use of an array instead of two different variables count0 and count1. Compare:

for (int exp = 0; exp &lt; digits; ++exp) {
    // Count elements
    size_t count0 = 0;
    size_t count1 = 0;
    for (size_t i = 0; i &lt; size; ++i) {
        if ((a[i] &gt;&gt; exp) &amp; 1) {
            count1 += 1;
        } else {
            count0 += 1;
        }
    }

    // Cumulative sum
    count1 += count0;

    // Build output array
    for (int i = size - 1; i &gt;= 0; --i) {
        if ((a[i] &gt;&gt; exp) &amp; 1) {
            b[--count1] = a[i];
        } else {
            b[--count0] = a[i];
        }
    }
    int *p = a; a = b; b = p;
}




After rewriting like this, it becomes apparent that after the first loop, count0 + count1 == size; and after the "Cumulative sum" step, count1 == size. So we can eliminate half of the code.

    size_t count0 = 0;
    size_t count1 = size;
    for (size_t i = 0; i &lt; size; ++i) {
        if (((a[i] &gt;&gt; exp) &amp; 1) == 0) {
            count0 += 1;
        }
    }

    // Build output array
    for (int i = size - 1; i &gt;= 0; --i) {
        if ((a[i] &gt;&gt; exp) &amp; 1) {
            b[--count1] = a[i];
        } else {
            b[--count0] = a[i];
        }
    }


Then, the "Build output array" step is doing the exact same workload (a[i] &gt;&gt; exp) &amp; 1 a second time! That seems like a fruitful source of optimization. What if you folded the second loop into the first loop, something like this?

for (int exp = 0; exp &lt; digits; ++exp) {
    size_t up = 0;
    size_t down = size;
    for (size_t i = 0; i &lt; size; ++i) {
        int x = a[i];
        if ((x &gt;&gt; exp) &amp; 1) {
            b[--down] = x;
        } else {
            b[up++] = x;
        }
    }
    assert(up == down);
    // Now elements [up..size) are in reversed order,
    // so we need to flip them back around.
    reverse_array(b + up, b + size);
    int *temp = a; a = b; b = temp;
}


Writing reverse_array is left as an exercise for the reader.

I'd be interested to see your benchmark results for this "improved" algorithm.