Function radix_sort7

StereoKitC/systems/render.cpp:1448–1505

}

void radix_sort7(render_item_t *a, size_t count) {
	// Resize up if needed
	if (radix_queue_size < count) {
		sk_free(radix_queue_area);
		radix_queue_area = sk_malloc_t(render_item_t, count);
		radix_queue_size = count;
	}
	freq_array_type freqs = {};
	count_frequency(a, count, freqs);

	render_item_t *from = a, *to = radix_queue_area;

	for (size_t pass = 0; pass < RADIX_LEVELS; pass++) {

		if (is_trivial(freqs[pass], count)) {
			// this pass would do nothing, just skip it
			continue;
		}

		uint64_t shift = pass * RADIX_BITS;

		// array of pointers to the current position in each queue, which we set up based on the
		// known final sizes of each queue (i.e., "tighly packed")
		render_item_t *queue_ptrs[RADIX_SIZE], *next = to;
		for (size_t i = 0; i < RADIX_SIZE; i++) {
			queue_ptrs[i] = next;
			next += freqs[pass][i];
		}

		// copy each element into the appropriate queue based on the current RADIX_BITS sized
		// "digit" within it
		for (size_t i = 0; i < count; i++) {
			render_item_t value = from[i];
			size_t        index = (value.sort_id >> shift) & RADIX_MASK;
			*queue_ptrs[index]++ = value;
#ifdef _MSC_VER
	#if defined(_M_ARM) || defined(_M_ARM64)
			__prefetch (queue_ptrs[index] + 1);
	#else
			_m_prefetch(queue_ptrs[index] + 1);
	#endif
#else
			__builtin_prefetch(queue_ptrs[index] + 1);
#endif
		}

		// swap from and to areas
		render_item_t *tmp = to;
		to   = from;
		from = tmp;
	}

	// because of the last swap, the "from" area has the sorted payload: if it's
	// not the original array "a", do a final copy
	if (from != a) {
		memcpy(a, from, count*sizeof(render_item_t));
	}
}