radix_sorts.h

/* Some neat resources */
/* radix sort from: https://www.geeksforgeeks.org/radix-sort/*/
/* radix sort from: https://github.com/gorset/radix/blob/master/radix.cc*/
/* radix sort from: https://www.quora.com/What-is-the-most-efficient-way-to-sort-a-million-32-bit-integers*/
/* radix sort from: http://pseudoprogrammer.blogspot.com/2012/05/binary-radix-sort.html*/
/*// the template
void radix_sort(unsigned *begin, unsigned *end)
{
	unsigned *begin1 = new unsigned[end - begin];
	unsigned *end1 = begin1 + (end - begin);
	for (unsigned shift = 0; shift < 32; shift += 8) {
		size_t count[0x100] = {};
		for (unsigned *p = begin; p != end; p++)
			count[(*p >> shift) & 0xFF]++;
		unsigned *bucket[0x100], *q = begin1;
		for (int i = 0; i < 0x100; q += count[i++])
			bucket[i] = q;
		for (unsigned *p = begin; p != end; p++)
			*bucket[(*p >> shift) & 0xFF]++ = *p;
		std::swap(begin, begin1);
		std::swap(end, end1);
	}
	delete[] begin1;
}
*/
void radix_sort(unsigned char* begin, unsigned char* end) {
	unsigned char *begin1 = new unsigned char[end - begin];
	unsigned char *end1 = begin1 + (end - begin);
	unsigned bit_depth = sizeof(unsigned char) * 8;
	//technically...this only runs once... (unsigned char is 8 bits and all)
	for (unsigned long shift = 0; shift < bit_depth; shift += 8) {
		size_t count[0x100] = {};
		for (unsigned char *p = begin; p != end; p++)
			count[(*p >> shift) & 0xFF]++;
		unsigned char *bucket[0x100];
		unsigned char *q = begin1;
		for (int i = 0; i < 0x100; q += count[i++])
			bucket[i] = q;
		for (unsigned char*p = begin; p != end; p++)
			*bucket[(*p >> shift) & 0xFF]++ = *p;
		std::swap(begin, begin1);
		std::swap(end, end1);
	}
}

void radix_sort(unsigned short *begin, unsigned short *end) {
	unsigned short *begin1 = new unsigned short[end - begin];
	unsigned short *end1 = begin1 + (end - begin);
	unsigned bit_depth = sizeof(unsigned short) * 8;
	for (unsigned long shift = 0; shift < bit_depth; shift += 8) {
		size_t count[0x100] = {};
		for (unsigned short *p = begin; p != end; p++)
			count[(*p >> shift) & 0xFF]++;
		unsigned short *bucket[0x100];
		unsigned short *q = begin1;
		for (int i = 0; i < 0x100; q += count[i++])
			bucket[i] = q;
		for (unsigned short*p = begin; p != end; p++)
			*bucket[(*p >> shift) & 0xFF]++ = *p;
		std::swap(begin, begin1);
		std::swap(end, end1);
	}
}

void radix_sort(unsigned long *begin, unsigned long *end) {
	unsigned long *begin1 = new unsigned long[end - begin];
	unsigned long *end1 = begin1 + (end - begin);
	unsigned bit_depth = sizeof(unsigned long) * 8;
	for (unsigned long shift = 0; shift < bit_depth; shift += 8) {
		size_t count[0x100] = {};
		for (unsigned long *p = begin; p != end; p++)
			count[(*p >> shift) & 0xFF]++;
		unsigned long *bucket[0x100];
		unsigned long *q = begin1;
		for (int i = 0; i < 0x100; q += count[i++])
			bucket[i] = q;
		for (unsigned long*p = begin; p != end; p++)
			*bucket[(*p >> shift) & 0xFF]++ = *p;
		std::swap(begin, begin1);
		std::swap(end, end1);
	}
	delete[] begin1;
}

void radix_sort(unsigned long long *begin, unsigned long long *end) {
	unsigned long long *begin1 = new unsigned long long[end - begin];
	unsigned long long *end1 = begin1 + (end - begin);
	unsigned bit_depth = sizeof(unsigned long long) * 8;
	for (unsigned shift = 0; shift < bit_depth; shift += 8) {
		size_t count[0x100] = {};
		for (unsigned long long *p = begin; p != end; p++)
			count[(*p >> shift) & 0xFF]++;
		unsigned long long *bucket[0x100], *q = begin1;
		for (int i = 0; i < 0x100; q += count[i++])
			bucket[i] = q;
		for (unsigned long long*p = begin; p != end; p++)
			*bucket[(*p >> shift) & 0xFF]++ = *p;
		std::swap(begin, begin1);
		std::swap(end, end1);
	}
	delete[] begin1;
}