mergesort.go

package main

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

func main() {
	x := rand.Perm(1000)
	var y []int
	y = append(y, x...)

	mergeStart := time.Now()
	mergeSort(x)
	mergeTime := time.Since(mergeStart)

	parallelStart := time.Now()
	parallelMergeSort(y, nil)
	parallelTime := time.Since(parallelStart)

	fmt.Printf("time to sort:\n")
	fmt.Printf("\tSequential: %v\n", mergeTime)
	fmt.Printf("\tParallel:   %v\n", parallelTime)
}

func mergeSort(slice []int) {
	if len(slice) <= 1 {
		return
	}

	var left, right []int
	left = append(left, slice[:len(slice)/2]...)
	right = append(right, slice[len(slice)/2:]...)

	mergeSort(left)
	mergeSort(right)

	var l, r int
	for i := range slice {
		if r >= len(right) || (l < len(left) && left[l] < right[r]) {
			slice[i] = left[l]
			l++
		} else {
			slice[i] = right[r]
			r++
		}
	}
}

func parallelMergeSort(slice []int, parentWg *sync.WaitGroup) {
	if parentWg != nil {
		defer parentWg.Done()
	}
	if len(slice) <= 1 {
		return
	}

	var left, right []int
	left = append(left, slice[:len(slice)/2]...)
	right = append(right, slice[len(slice)/2:]...)

	// don't do it in parallel if the slice is small
	if len(slice) < 50 {
		parallelMergeSort(left, nil)
		parallelMergeSort(right, nil)
	} else {
		wg := new(sync.WaitGroup)
		wg.Add(2)
		go parallelMergeSort(left, wg)
		go parallelMergeSort(right, wg)
		wg.Wait()
	}

	var l, r int
	for i := range slice {
		if r >= len(right) || (l < len(left) && left[l] < right[r]) {
			slice[i] = left[l]
			l++
		} else {
			slice[i] = right[r]
			r++
		}
	}
}