go parallel quick sort

main.go

package main

import (
	"fmt"
	"math/rand"
	"sort"
	"sync"
	"time"
)

const chunk_size = 500

func pqs(array []int, i, j int) {
	if sort.IntsAreSorted(array[i:j]) {
		return
	}
	if j-i <= chunk_size {
		go sort.Ints(array[i:j])
		return
	}
	pivot := array[i]
	pivot_index := i
	var pivot_mutex sync.Mutex
	var pivot_wg sync.WaitGroup
	pivot_ranges := ranges(i, j, chunk_size)
	for _, r := range pivot_ranges {
		pivot_wg.Add(1)
		go func(r rng) {
			defer pivot_wg.Done()
			pivot_offset := 0
			for k := r.begin; k < r.end; k++ {
				if array[k] < pivot {
					pivot_offset++
				}
			}
			pivot_mutex.Lock()
			pivot_index += pivot_offset
			pivot_mutex.Unlock()
		}(r)
	}
	pivot_wg.Wait()
	p := array[pivot_index]
	array[i] = p
	array[pivot_index] = pivot

	lower := ranges(i, pivot_index, chunk_size)
	upper := ranges(pivot_index+1, j, chunk_size)
	var shuffle_mutex sync.Mutex
	var shuffle_wg sync.WaitGroup
	if len(lower) == 0 {
		pqs(array, pivot_index+1, j)
		return
	}
	if len(upper) == 0 {
		pqs(array, i, pivot_index)
		return
	}
	for true {
		shuffle_wg.Wait()
		if len(lower) == 0 || len(upper) == 0 {
			break
		}
		shuffle_mutex.Lock()
		l := lower[0]
		lower = lower[1:]
		u := upper[0]
		upper = upper[1:]
		shuffle_mutex.Unlock()
		shuffle_wg.Add(1)
		go func(ll rng, uu rng) {
			defer shuffle_wg.Done()
			ii := ll.begin
			jj := uu.begin
			for ii < ll.end && jj < uu.end {
				if array[ii] >= pivot {
					if array[jj] < pivot {
						a, b := array[ii], array[jj]
						array[ii], array[jj] = b, a
						ii += 1
						jj += 1
					} else {
						jj += 1
					}
				} else {
					ii += 1
				}
			}
			if ii < ll.end {
				shuffle_mutex.Lock()
				lower = append(lower, rng{ii, ll.end})
				shuffle_mutex.Unlock()
			}
			if jj < uu.end {
				shuffle_mutex.Lock()
				upper = append(upper, rng{jj, uu.end})
				shuffle_mutex.Unlock()
			}
		}(l, u)
	}
	var recurse_wg sync.WaitGroup
	recurse_wg.Add(2)
	go func() {
		defer recurse_wg.Done()
		pqs(array, i, pivot_index)
	}()
	go func() {
		defer recurse_wg.Done()
		pqs(array, pivot_index+1, j)
	}()
	recurse_wg.Wait()
}

type rng struct {
	begin int
	end   int
}

func ranges(begin, end, step int) []rng {
	result := make([]rng, 0, ((end-begin)/step)+1)
	for begin+step < end {
		result = append(result, rng{begin, begin + step})
		begin += step
	}
	result = append(result, rng{begin, end})
	return result
}

func equals(a []int, b []int) bool {
	if len(a) != len(b) {
		return false
	}
	for i := 0; i < len(a); i++ {
		if a[i] != b[i] {
			return false
		}
	}
	return true
}

func main() {
	rand.Seed(time.Now().Unix())
	array := make([]int, 0)
	for i := 0; i <= 10000; i++ {
		n := rand.Intn(100000)
		array = append(array, n)
	}
	t0 := time.Now()
	pqs(array, 0, len(array))
	d0 := time.Since(t0)
	fmt.Println(d0)
}

main_test.go

package main

import (
	"fmt"
	"math/rand"
	"sort"
	"testing"
)

func TestRanges(t *testing.T) {
	r1 := ranges(0, 10, 2)
	expected1 := []rng{rng{0, 2}, rng{2, 4}, rng{4, 6}, rng{6, 8}, rng{8, 10}}
	for i := 0; i < len(r1); i++ {
		if r1[i] != expected1[i] {
			t.Errorf("Error on index: %d", i)
		}
	}

	r2 := ranges(0, 10, 3)
	expected2 := []rng{rng{0, 3}, rng{3, 6}, rng{6, 9}, rng{9, 10}}
	for i := 0; i < len(r2); i++ {
		if r2[i] != expected2[i] {
			t.Errorf("Error on index: %d", i)
		}
	}

}

func BenchmarkSort(b *testing.B) {
	// these numbers come out quite nicely in a log scale
	sizes := []int{
		10e2, 3 * 10e2, 7 * 10e2,
		10e3, 3 * 10e3, 7 * 10e3,
		10e4, 3 * 10e4, 7 * 10e4,
		10e5, 3 * 10e5, 7 * 10e5,
		10e6, 3 * 10e6, 7 * 10e6,
		10e7, 3 * 10e7, 7 * 10e7}
	for _, size := range sizes {
		array := make([]int, size)
		for j := 0; j < size; j++ {
			array[j] = rand.Intn(100000)
		}
		b.Run(fmt.Sprintf("ParallelQuickSort/%d", size), func(b *testing.B) {
			b.ReportAllocs()
			var j = make([]int, size)
			b.ResetTimer()
			for i := 0; i < b.N; i++ {
				b.StopTimer()
				copy(j, array)
				b.StartTimer()

				pqs(j[:], 0, size)
			}
		})
		b.Run(fmt.Sprintf("StdlibSort/%d", size), func(b *testing.B) {
			b.ReportAllocs()
			var j = make([]int, size)
			b.ResetTimer()
			for i := 0; i < b.N; i++ {
				b.StopTimer()
				copy(j, array)
				b.StartTimer()

				sort.Ints(j)
			}
		})
	}

}