quicksort in go

qsort.go

package main

import (
	"fmt"
	"math/rand"
	"os"
	"runtime"
	"runtime/trace"
	"sync"
	"time"
)

func qSort(data []int) {
	if len(data) < 2 {
		return
	}
	pivot := data[0]
	left, right := 1, len(data)-1
	for right >= left {
		if data[left] <= pivot {
			left++
		} else {
			data[right], data[left] = data[left], data[right]
			right--
		}
	}
	// swap pivot into middle
	data[left-1], data[0] = data[0], data[left-1]
	qSort(data[:left-1])
	qSort(data[left:])
}

const thresh = 1e3

func qSortPar(data []int, wg *sync.WaitGroup) {
	if len(data) < 2 {
		// should have bailed to qSort by now but still
		wg.Done()
		return
	}
	pivot := data[0]
	left, right := 1, len(data)-1
	for right >= left {
		if data[left] <= pivot {
			left++
		} else {
			data[right], data[left] = data[left], data[right]
			right--
		}
	}
	// swap pivot into middle
	data[left-1], data[0] = data[0], data[left-1]

	// launch tasks for big subsorts
	if left-1 > thresh {
		wg.Add(1)
		go qSortPar(data[:left-1], wg)
	}
	if len(data)-right > thresh {
		wg.Add(1)
		go qSortPar(data[left:], wg)
	}

	// do small subsorts now
	if left-1 <= thresh {
		qSort(data[:left-1])
	}
	if len(data)-right <= thresh {
		qSort(data[left:])
	}

	// we're done
	wg.Done()
}

func quicksort(data []int) {
	wg := new(sync.WaitGroup)
	wg.Add(1)
	qSortPar(data, wg)
	wg.Wait()
}

func main() {
	runtime.GOMAXPROCS(4)
	data := make([]int, 1e5)

	for i := range data {
		data[i] = int(rand.Uint32() >> 1)
	}
	t := time.Now()
	f, err := os.Create("trace.out")
	if err != nil {
		panic(err.Error())
	}
	defer f.Close()
	trace.Start(f)
	quicksort(data)
	for i := range data[1:] {
		if data[i] > data[i+1] {
			fmt.Println("not sorted at index", i)
			panic("not sorted")
		}
	}
	trace.Stop()
}

Disclaimer: I found this code on SO, but I can't find the answer I copied it from! If this is your code, please reply here so you can be credited.

This won't compile. Need to remove 10 and 90 lines.