radix sort adopted from questdb

radix.go

// RadixSort ...
// credits QuestDB impl for radix sort (7104a57)
// core/src/main/c/share/ooo.cpp
func RadixSort(array []uint64) {
	if len(array) <= 100 {
		insertionSort(array)
		return
	}
	// counts
	type rscounts struct {
		c8 [256]uint64
		c7 [256]uint64
		c6 [256]uint64
		c5 [256]uint64
		c4 [256]uint64
		c3 [256]uint64
		c2 [256]uint64
		c1 [256]uint64
	}
	var counts rscounts
	var o8, o7, o6, o5, o4, o3, o2, o1 uint64
	var t8, t7, t6, t5, t4, t3, t2, t1 uint64

	// calculate counts
	for x := 0; x < len(array); x++ {
		t8 = array[x] & 0xFF
		t7 = (array[x] >> 8) & 0xFF
		t6 = (array[x] >> 16) & 0xFF
		t5 = (array[x] >> 24) & 0xFF
		t4 = (array[x] >> 32) & 0xFF
		t3 = (array[x] >> 40) & 0xFF
		t2 = (array[x] >> 48) & 0xFF
		t1 = (array[x] >> 56) & 0xFF
		counts.c8[t8]++
		counts.c7[t7]++
		counts.c6[t6]++
		counts.c5[t5]++
		counts.c4[t4]++
		counts.c3[t3]++
		counts.c2[t2]++
		counts.c1[t1]++
	}

	// convert counts to offsets
	for x := 0; x < 256; x++ {
		t8 = o8 + counts.c8[x]
		t7 = o7 + counts.c7[x]
		t6 = o6 + counts.c6[x]
		t5 = o5 + counts.c5[x]
		t4 = o4 + counts.c4[x]
		t3 = o3 + counts.c3[x]
		t2 = o2 + counts.c2[x]
		t1 = o1 + counts.c1[x]
		counts.c8[x] = o8
		counts.c7[x] = o7
		counts.c6[x] = o6
		counts.c5[x] = o5
		counts.c4[x] = o4
		counts.c3[x] = o3
		counts.c2[x] = o2
		counts.c1[x] = o1
		o8 = t8
		o7 = t7
		o6 = t6
		o5 = t5
		o4 = t4
		o3 = t3
		o2 = t2
		o1 = t1
	}

	cpy := make([]uint64, len(array))
	radixShuffle(counts.c8, array, cpy, 0)
	radixShuffle(counts.c7, cpy, array, 8)
	radixShuffle(counts.c6, array, cpy, 16)
	radixShuffle(counts.c5, cpy, array, 24)
	radixShuffle(counts.c4, array, cpy, 32)
	radixShuffle(counts.c3, cpy, array, 40)
	radixShuffle(counts.c2, array, cpy, 48)
	radixShuffle(counts.c1, cpy, array, 56)
}

func radixShuffle(counts [256]uint64, src, dst []uint64, sh uint16) {
	for x := 0; x < len(src); x++ {
		digit := src[x] >> sh & 0xFF
		dst[counts[digit]] = src[x]
		counts[digit]++
	}
}

func insertionSort(array []uint64) {
	var n = len(array)
	for i := 1; i < n; i++ {
		j := i
		for j > 0 {
			if array[j-1] > array[j] {
				array[j-1], array[j] = array[j], array[j-1]
			}
			j = j - 1
		}
	}
}