radix-sort for 32-bit 2's-compliment integers. Implemented a homegrown clone of of std's stable_partition.

radix_sort_test.cpp

#include <iostream>
#include <functional>
#include <iterator>
#include <vector>

struct Node {
	Node* next = nullptr;
	int data;
};

void stable_partition(int* start, int *end, std::function<bool(int)> partitioner) {
	// Trivial case
	if ((start + 1) >= end) {
		return;
	}

	const long LENGTH = end - start;
	std::vector<Node> node_pool(LENGTH);

	Node *low_head = nullptr;
	Node *low_tail = nullptr;

	Node *high_head = nullptr;
	Node *high_tail = nullptr;

	for (int *i = start; i != end; i++) {
		Node *node_ptr = &node_pool[i - start];
		node_ptr->data = *i;

		if (partitioner(*i)) {
			// Low List
			if (low_head == nullptr) {
				low_head = low_tail = node_ptr;
			} else {
				low_tail->next = node_ptr;
				low_tail = node_ptr;
			}
		} else {
			// High list
			if (high_head == nullptr) {
				high_head = high_tail = node_ptr;
			} else {
				high_tail->next = node_ptr;
				high_tail = node_ptr;
			}
		}
	}

	// No Lows
	if (low_head == nullptr) {
		low_head = high_head;
	} else {
		low_tail->next = high_head;
	}

	Node *curr = low_head;
	for (int step = 0; step < LENGTH; step++) {
		start[step] = curr->data;
		curr = curr->next;
	}
}

// Least significant digit radix sort for two's compliment 32-bit ints
void radix_sort(int *first, int *last_exclusive) {
	for (int low_bit = 0; low_bit < 31; low_bit++) {
		stable_partition(first, last_exclusive, [low_bit](int value) {
			auto bit = value & (1 << low_bit);
			return !bit;
		});
	}

	stable_partition(first, last_exclusive, [](int value) {
		return value < 0;
	});
}

// test radix_sort
int main()
{
	int data[] = { 170, 45, 75, -90, -802, 24, 2, 66 };

	radix_sort(data, data + 8);

	std::copy(data, data + 8, std::ostream_iterator<int>(std::cout, " "));

	std::cout << std::endl;

	std::cin.ignore();

	return 0;
}