make_results.sh

#/usr/bin/env bash
cmd="go test -bench=."
(echo '$' $cmd; $cmd) | tee results.txt

qs.go

package main

import (
	"sort"
	"sync"
)

func partition(v []int) int {
	x := v[0]
	i := 1
	j := len(v) - 1
	for j >= i {
		if v[i] <= x {
			v[i-1] = v[i]
			i++
			continue
		}
		if v[j] >= x {
			j--
			continue
		}
		v[i-1] = v[j]
		v[j] = v[i]
		i++
		j--
	}
	v[j] = x
	return j
}

func QuickSortNative(v []int) {
	sort.Ints(v)
}

func QuickSortSingleThreaded(v []int) {
	if len(v) <= 1 {
		return
	}
	p := partition(v)
	QuickSortSingleThreaded(v[:p])
	QuickSortSingleThreaded(v[p+1:])
}

func QuickSortMultiThreaded(v []int) {
	var wg sync.WaitGroup
	wg.Add(1)
	quickSortMultiThreadedImpl(v, 9, &wg)
	wg.Wait()
}

func quickSortMultiThreadedImpl(v []int, depth int, wg *sync.WaitGroup) {
	if wg != nil {
		defer wg.Done()
	}
	if len(v) <= 1 {
		return
	}
	p := partition(v)
	if depth > 0 {
		var innerWg sync.WaitGroup
		innerWg.Add(1)
		go quickSortMultiThreadedImpl(v[p+1:], depth-1, &innerWg)
		quickSortMultiThreadedImpl(v[:p], depth-1, nil)
		innerWg.Wait()
	} else {
		QuickSortSingleThreaded(v[:p])
		QuickSortSingleThreaded(v[p+1:])
	}
}

qs_test.go

package main

import (
	"errors"
	"log"
	"testing"
)

var (
	rnd_state int = 0
)

func rnd() int {
	rnd_state = (rnd_state*13 + 37) % 1000000000000037
	return rnd_state
}

func check(v []int) error {
	for i := 0; i < len(v)-1; i++ {
		if v[i] > v[i+1] {
			return errors.New("Unsorted array!")
		}
	}
	return nil
}

func bench(b *testing.B, fn func(v []int)) {
	v := make([]int, 1000000)
	b.StopTimer()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		for j := 0; j < len(v); j++ {
			v[j] = rnd()
		}
		b.StartTimer()
		fn(v)
		b.StopTimer()
		if err := check(v); err != nil {
			log.Fatal(err)
		}
	}
}

func BenchmarkNative(b *testing.B) {
	bench(b, QuickSortNative)
}

func BenchmarkSingleThreaded(b *testing.B) {
	bench(b, QuickSortSingleThreaded)
}

func BenchmarkRadix(b *testing.B) {
	bench(b, RadixSort)
}

func BenchmarkMultiThreaded(b *testing.B) {
	bench(b, QuickSortMultiThreaded)
}

radix.go

package main

func radixSinglePass(v []int, mask int, shift uint, counts, u []int) {
	for i := range(counts) {
		counts[i] = 0
	}
	for _, x := range(v) {
		digit := (x >> shift) & mask
		counts[digit]++
	}
	for i := 1; i < len(counts); i++ {
		counts[i] += counts[i - 1]
	}

	copy(u, v)
	for i := len(u) - 1; i >= 0; i-- {
		digit := (u[i] >> shift) & mask
		counts[digit]--
		v[counts[digit]] = u[i]
	}
}

func RadixSort(v []int) {
	var digitSize uint = 8
	digitSize = 8
	counts := make([]int, 1 << digitSize)
	u := make([]int, len(v))
	mask := (1 << digitSize) - 1
	var shift uint
	for shift = 0; shift < 64; shift += digitSize {
		radixSinglePass(v, mask, shift, counts, u)
	}
}

results.txt

$ go test -bench=.
goos: darwin
goarch: amd64
BenchmarkNative-8           	       5	 200466249 ns/op
BenchmarkSingleThreaded-8   	      20	  89499892 ns/op
BenchmarkRadix-8            	      20	  58155085 ns/op
BenchmarkMultiThreaded-8    	      50	  25495066 ns/op
PASS
ok  	_/Users/kawakami/temp/discord-help/amumu/go	6.210s