golang mergesort, threaded

gistfile1.go

package gosort

import (
	"math/rand"
	"time"
	"runtime"
	//Extra for profiling
	//"testing"
	"runtime/pprof"
	"flag"
	"os"
	"log"
)

var cpuprofile = flag.String("cpuprofile", "", "write cpu profile to file")

var THRESHOLD = 20000

func FillRandSplice(arr []int) {
	rand.Seed(time.Now().UnixNano())
	for i := 0; i < len(arr); i++ {
		arr[i] = rand.Intn(1e5)
	}
}

func checkSorted(arr []int) bool {
	last := 0
	for i := range arr {
		if i < last {
			return false
		}
		last = i
	}
	return true
}

func merge(left, right, buffer []int) {
	leftIter := 0
	rightIter := 0
	for sortIter := 0;sortIter < len(buffer);sortIter++ {
		if leftIter < len(left) && rightIter < len(right) {
			if left[leftIter] > right[rightIter] {
				buffer[sortIter] = right[rightIter]
				rightIter++
			} else {
				buffer[sortIter] = left[leftIter]
				leftIter++
			}
		} else {
			if leftIter < len(left) {
				buffer[sortIter] = left[leftIter]
				leftIter++
			} else if rightIter < len(right) {
				buffer[sortIter] = right[rightIter]
				rightIter++
			}
		}
	}
	combined := left[:len(buffer)]
	for i:=0; i < len(buffer); i++ {
		combined[i] = buffer[i]
	}
}

func mergeSort(arr []int) {
	mid := len(arr)/2
	buffer := make([]int, len(arr))
	_mergeSort(arr[:mid], arr[mid:],buffer)
}

func _mergeSort(left, right, buffer []int) {
	lefLen := len(left)
	rightLen := len(right);
	if lefLen > 0 && rightLen > 0 {
		_mergeSort(left[:lefLen/2], left[lefLen/2:], buffer[:len(left)])
		_mergeSort(right[:rightLen/2], right[rightLen/2:], buffer[len(left):])
		merge(left, right, buffer)
	}
}

func GoSortRecur(left, right, buffer []int, depth int, signal chan<- bool) {
	lc := make(chan bool)
	rc := make(chan bool)
	if depth < 2 {
		go GoSortRecur(left[:len(left)/2],left[len(left)/2:],buffer[:len(left)], depth + 1, lc)
		go GoSortRecur(right[:len(right)/2], right[len(right)/2:],buffer[len(left):], depth + 1,  rc)
		<-lc
		<-rc
		merge(left, right, buffer)
	} else {
		_mergeSort(left,right, buffer)
	}

	signal<- true
}

func GoSort(arr []int) {
	done := make(chan bool)
	buffer := make([]int, len(arr))
	go GoSortRecur(arr[:len(arr)/2],arr[len(arr)/2:],buffer, 0, done)
	<-done
}

func bubbleSort(arr []int) {
	for i := 0; i < len(arr); i++ {
		for j := len(arr) - 1; j > i; j-- {
			if arr[i] > arr[j] {
				arr[i], arr[j] = arr[j], arr[i]
			}
		}
	}
}


func main() {
	flag.Parse()
	//Initialize array before starting profiling
	runtime.GOMAXPROCS(8)

	num := 40000000
	arr := make([]int, num)
	FillRandSplice(arr)
	if *cpuprofile != "" {
		f, err := os.Create(*cpuprofile)
		if err != nil {
			log.Fatal(err)
		}
		pprof.StartCPUProfile(f)
		defer pprof.StopCPUProfile()
	}
	GoSort(arr)
	if !checkSorted(arr) {
		log.Fatal("improperly sorted!")
	}
}