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
	quickSortMultiThreadedImpl(v, 9, &wg)
	wg.Wait()
}

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

qs_test.go

package main

import (
	"log"
	"errors"
	"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] {
			log.Println(v)
			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 BenchmarkMultiThreaded(b *testing.B) {
	bench(b, QuickSortMultiThreaded)
}

result.txt

$ go test -bench=.
goos: darwin
goarch: amd64
BenchmarkNative-8           	      10	 199269460 ns/op
BenchmarkSingleThreaded-8   	      20	  92672305 ns/op
BenchmarkMultiThreaded-8    	      50	  25983851 ns/op
PASS
ok  	_/Users/kawakami/temp/discord-help/amumu/go	5.960s