Radix sort for Odin

radix.odin

package radix

/*
NOTE:
This radix implementation requires a slice of uniformly signed integers, either all negative or all positive.
There is a check for type being unsigned, because most likely you do not want to sort a slice of negative numbers.
In case you do - you can remove that check.

In non-optimized build radix sort is more or less the same speed as default sort for 64bit integers.
In optimized build radix sort is twice as fast as default sort for 64bit integers (on my computer).
32bit numbers are always sorted twice as fast as 64, 16 twice as fast as 32, 8 twice as fast as 16.
*/

import "core:fmt"
import "core:time"
import "core:slice"
import "core:math/rand"
import "core:intrinsics"

radix_sort :: proc(arr: []$T, allocator := context.temp_allocator)
where intrinsics.type_is_integer(T) && intrinsics.type_is_unsigned(T)
{
	SIZE_BYTES :: size_of(T)

	arr := arr
	arr_len := len(arr)
	tmp_arr := make([]T, arr_len, allocator)

	for byte_index in uint(0)..<SIZE_BYTES {
		counts: [256]uint
		for v in arr {
			piece := (v >> (byte_index * 8)) & 0xff
			counts[piece] += 1
		}

		total: uint
		for v in &counts {
			count := v
			v = total
			total += count
		}

		for v in arr {
			piece := (v >> (byte_index * 8)) & 0xff
			tmp_arr[counts[piece]] = v
			counts[piece] += 1
		}

		slice.swap_between(arr, tmp_arr)
	}

	return
}

main :: proc() {
	stopwatch: time.Stopwatch
	arr := make([]u64, 100_00)
	lowest: time.Duration

	lowest = max(time.Duration)
	for i in 0..<100 {
		for v in &arr {
			v = auto_cast(rand.uint32() % 1000)
		}

		time.stopwatch_reset(&stopwatch)
		time.stopwatch_start(&stopwatch)
		radix_sort(arr)
		time.stopwatch_stop(&stopwatch)

		assert(slice.is_sorted(arr))
		lowest = min(lowest, time.stopwatch_duration(stopwatch))
	}
	fmt.println("radix", lowest)

	lowest = max(time.Duration)
	for i in 0..<100 {
		for v in &arr {
			v = auto_cast(rand.uint32() % 1000)
		}

		time.stopwatch_reset(&stopwatch)
		time.stopwatch_start(&stopwatch)
		slice.sort(arr)
		time.stopwatch_stop(&stopwatch)

		assert(slice.is_sorted(arr))
		lowest = min(lowest, time.stopwatch_duration(stopwatch))
	}
	fmt.println("default", lowest)
}