radix_sort.c

#include <stdio.h>
#include <assert.h>

struct item_t
{
	int key;
	int val;
};

int get_byte(int val, int byte_index)
{
	return (val >> (8 * byte_index)) & 0xFF;
}

// Flip the sign bit so negative numbers aren't treating as ginormous.
int get_key(int val)
{
	return val ^ (1 << 31);
}

// O(N * k) sort where k is width of `int`.
// This is faster than O(N * Log(N)) since the sort predicate returns more
// than one bit of information, as opposed to e.g. < operator.
// Resource: https://hero.handmade.network/forums/code-discussion/t/984-day_229__what_about_radix_sort
void radix_sort(item_t* src, item_t* temp, int n)
{
	// Count all frequencies of each byte.
	int counts[4][256] = { 0 };
	for (int i = 0; i < n; ++i) {
		int key = get_key(src[i].key);
		counts[0][get_byte(key, 0)]++;
		counts[1][get_byte(key, 1)]++;
		counts[2][get_byte(key, 2)]++;
		counts[3][get_byte(key, 3)]++;
	}

	// Transform to prefix sum format. Shift elements to the right one index.
	// This informs us of where the solution goes in the final answer.
	for (int i = 0; i < 4; ++i) {
		int total = 0;
		for (int j = 0; j < 256; j++) {
			int count = counts[i][j];
			counts[i][j] = total;
			total += count;
		}
	}

	// Fill in the solution based on the prefix array.
	// Temp space is required for low branching and sort stability.
	for (int i = 0; i < 4; ++i) {
		for (int j = 0; j < n; j++) {
			int key = get_key(src[j].key);
			int byte = get_byte(key, i);
			temp[counts[i][byte]++] = src[j];
		}

		item_t* swap = src;
		src = temp;
		temp = swap;
	}
}

int main()
{
	item_t in[] = {
		{ 13, 0 },
		{ 5, 1 },
		{ 5, 2 },
		{ 3, 3 },
		{ 7, 4 },
		{ -3, 5 },
		{ -10, 6 },
		{ 1, 7 },
		{ 0, 8 },
		{ 2, 9 },
	};

	item_t temp[sizeof(in) / sizeof(in[0])];
	int n = sizeof(in) / sizeof(in[0]);

	radix_sort(in, temp, n);

	for (int i = 0; i < n; ++i) {
		printf("{ %d, %d }\n", in[i].key, in[i].val);
	}

	return 0;
}