Merge sort using coroutine. Not really parallel but just for fun

parallelMergeSort.go

package main

import (
	"bufio"
	"fmt"
	"math/rand"
	"os"
	"strconv"
	"strings"
	"sync"
)

// ParseInts convert a string of numbers to slice of number
func ParseInts(nums string) ([]int, error) {
	fields := strings.Fields(nums)
	arr := make([]int, len(fields))
	for i := 0; i < len(fields); i++ {
		var err error
		arr[i], err = strconv.Atoi(fields[i])
		if err != nil {
			return nil, err
		}
	}
	return arr, nil
}

// ReadInts read numbers from stdin and save to a slice
func ReadInts(msg string) ([]int, error) {
	reader := bufio.NewReader(os.Stdin)
	fmt.Print(msg)
	line, err := reader.ReadString('\n')
	if err != nil {
		return nil, err
	}
	return ParseInts(line)
}

/*
BubbleSort sort part of array using bubble sort
sort arr from index lo to index hi
*/
func BubbleSort(arr []int, lo, hi int) {
	//fmt.Printf("Prepare to sort from %d to %d: %v\n", lo, hi, arr[lo:hi+1])
	for i := lo; i <= hi; i++ {
		for j := lo; j <= lo+hi-i-1; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
}

// copyArray make a copy of src array from lo to hi
func copyArray(src []int, lo, hi int) []int {
	dst := make([]int, hi-lo+1)
	copy(dst, src[lo:hi+1])
	return dst
}

func mergeSorted(arr []int, lo1, hi1, lo2, hi2 int) {
	if arr[hi1] < arr[lo2] { // Already merged
		return
	}
	//merge from back to avoid shift
	targetHi := hi2
	arr2 := copyArray(arr, lo2, hi2)
	hi2 = len(arr2) - 1
	for hi1 >= lo1 && hi2 >= 0 {
		if arr[hi1] > arr2[hi2] {
			arr[targetHi] = arr[hi1]
			hi1--
		} else {
			arr[targetHi] = arr2[hi2]
			hi2--
		}
		targetHi--
	}
	// In case other array still have item (which is rare)
	for hi2 >= 0 {
		arr[targetHi] = arr2[hi2]
		hi2--
		targetHi--
	}
}

func mergeSort(arr []int, lo, hi, threshold int, pwg *sync.WaitGroup) {
	if pwg != nil {
		defer pwg.Done()
	}
	if hi-lo < threshold {
		BubbleSort(arr, lo, hi)
	} else {
		var mid = lo + (hi-lo)/2
		var wg sync.WaitGroup
		wg.Add(2)
		go mergeSort(arr, lo, mid, threshold, &wg)
		go mergeSort(arr, mid+1, hi, threshold, &wg)
		wg.Wait()
		mergeSorted(arr, lo, mid, mid+1, hi)
	}
}

/*
ParSort sort an array using goroutine
if len of arr <= threshold it will use BubbleSort to sort
otherwise devide array in to chunk and sort in parallel
*/
func ParSort(arr []int, threshold int) {
	if threshold < 1 {
		threshold = 1
	}
	mergeSort(arr, 0, len(arr)-1, threshold, nil)
}

// randomArr generate random array of length for testing
func randomArr(length int) []int {
	arr := make([]int, length)
	for i := 0; i < length; i++ {
		arr[i] = rand.Intn(1000)
	}
	return arr
}

func main() {
	arr, err := ReadInts("Enter a list of numbers (separate by space): ")
	if err != nil {
		fmt.Println("Invalid input: ", err)
		return
	}
	threshold := len(arr) / 4
	ParSort(arr, threshold)
	fmt.Println("Sorted: ", arr)
}

parallelMergeSort_test.go

package main

import (
	"math/rand"
	"reflect"
	"sort"
	"testing"
	"time"
)

// TestTestParSort make sure ParMerge run correctly
func TestParSort(t *testing.T) {
	rand.Seed(time.Now().UTC().UnixNano())
	arr := randomArr(20000 + rand.Intn(5))
	arr2 := copyArray(arr, 0, len(arr)-1)
	ParSort(arr, 100)
	sort.Ints(arr2)
	if !reflect.DeepEqual(arr, arr2) {
		t.Error("ParSort not sort correctly")
	}
}

//BenchmarkParSort parallel sort
func BenchmarkParSort(b *testing.B) {
	rand.Seed(time.Now().UTC().UnixNano())
	arr := randomArr(b.N)
	ParSort(arr, 100)
}

//BenchmarkMergeSort single thread sort
func BenchmarkMergeSort(b *testing.B) {
	rand.Seed(time.Now().UTC().UnixNano())
	arr := randomArr(b.N)
	mergeSort(arr, 0, len(arr)-1, len(arr), nil)
}