Hexadecimal radix to sort a list of 4-byte integers

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

#define MAX_SIZE 100

void radix_sort(int arr[], int n) {
    int buckets[16][MAX_SIZE];
    int bucket_count[16];
    int i, j, k, r, shift, pass, NOP = 8;
    int buffer[MAX_SIZE];

    for (pass = 0; pass < NOP; pass++) {
        for (i = 0; i < 16; i++)
            bucket_count[i] = 0;

        shift = pass * 4;
        for (i = 0; i < n; i++) {
            r = ((unsigned int)arr[i] >> shift) & 15;
            buckets[r][bucket_count[r]] = arr[i];
            bucket_count[r]++;
        }

        i = 0;
        for (k = 0; k < 16; k++) {
            for (j = 0; j < bucket_count[k]; j++) {
                buffer[i] = buckets[k][j];
                i++;
            }
        }

        for (i = 0; i < n; i++)
            arr[i] = buffer[i];
    }
}

int main() {
    int arr[MAX_SIZE];
    int n, i;

    scanf("%d", &n);

    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    radix_sort(arr, n);

    for (i = 0; i < n; i++)
        printf("%d\n", arr[i]);

    return 0;
}

The objective is a hexadecimal radix sort. This means the program should process 4 bits at a time and use 16 buckets for sorting. Ok, got that. My buffer array and number array will never exceed 100. I get it to sort but not in the correct order. This is the output I always get:

 - *14394
 - *-5905
 - *-12765
 -  *1193
 -  *-7496
 -  *================ execution result ================
 -  *1193
 -  *14394
 -  *-12765
 -  *-7496
 -  *-5905
 -  *====== differences from correct results ======
 -  *1,2d0
 -  *< 1193
 -  *< 14394
 -  *5a4,5
 -  *> 1193
 -  *> 14394

Where the negative numbers get put at the bottom of the list. Larger negative numbers should be at the top and the positive descending numbers below i.e.:

• -100
• -10
• 0
• 10
• 100

I'm not exactly sure how to achieve this result. I saw a solution on SO for handling negatives in radix that said treat the sign as a special kind of digit but the poster did not specify. I feel I'm on the right track I just need it to sort properly but my attempts to change the logic have been causing huge bugs and all zero results.

The basic issue is that you are not sorting the input numbers by their own values. You are sorting them by the values resulting from conversion to unsigned int. That conversion even appears explicitly in your code. The result is that the signed values end up ordered from zero to most positive, followed by most negative to least negative.

If you want to sort numbers of signed type by their own numeric values then radix sort is not a clean fit. At minimum, you need to make some kind of special accommodation for the signs.

I saw a solution on SO for handling negatives in radix that said treat the sign as a special kind of digit but the poster did not specify.

One way to think about the sign bit is that it has a negative place value of larger magnitude than the (positive) place values of all of the other bits. For example, in 8-bit two's complement, the bits' place values can be construed as

That makes any set of contiguous bits containing the sign bit qualitatively different from all those that do not contain the sign bit.

Consider these bit patterns:

Observe that a base-2 (bit-by-bit) radix sort would be straightforward -- normal except that the sense of the comparisons for the sign bits needs to be reversed on account of the negative place value of that bit.

You can use that in your sort by implementing the following changes:

• in the main sort loop, sort by the 31 ordinary value bits only. That's an easy enough change:

          unsigned int magnitude_mask = ~0u >> 1;
          // ...
  
              r = ((magnitude_mask & (unsigned int) arr[i]) >> shift) & 0xf;
  

• after the main sort loop, perform one extra pass in which you sort in reverse by the sign bit. There are multiple ways to think about and implement that, but one would be to use the same code as the main loop, except for calculating r like so:

              r = (~(unsigned int) arr[i]) >> 31;
  

  The bitwise negation effects the "in reverse" part in that case.