concurrent merge sort

benchmark_results.sh

goos: darwin
goarch: amd64
pkg: puzzles-golang/algos/mergesort
BenchmarkConcurrentMergeSort_20-12        	  100000	     15146 ns/op
BenchmarkConcurrentMergeSort_50-12        	   50000	     32069 ns/op
BenchmarkConcurrentMergeSort_80-12        	   30000	     49633 ns/op
BenchmarkConcurrentMergeSort_200-12       	   10000	    104311 ns/op
BenchmarkConcurrentMergeSort_500-12       	   10000	    221560 ns/op
BenchmarkConcurrentMergeSort_5000-12      	     500	   2779299 ns/op
BenchmarkConcurrentMergeSort_100000-12    	      20	  57669829 ns/op
BenchmarkStdMergeSort_20-12               	 2000000	       862 ns/op
BenchmarkStdMergeSort_50-12               	  500000	      2565 ns/op
BenchmarkStdMergeSort_80-12               	  300000	      4462 ns/op
BenchmarkStdMergeSort_200-12              	  100000	     13663 ns/op
BenchmarkStdMergeSort_500-12              	   30000	     45032 ns/op
BenchmarkStdMergeSort_5000-12             	    2000	    738091 ns/op
BenchmarkStdMergeSort_100000-12           	     100	  18417434 ns/op

mergesort_concurrent.go

package mergesort

//  This is the modified merge sort using go concurrency
// if A of length 2x is split into X & Y of size x each,
// sorting of these can take place concurrently.

func SortConcurrent(arr []int) []int {
	ch := make(chan int, len(arr))
	sortConcurrentIntoChannel(arr, ch)
	var sorted []int
	for v := range ch {
		sorted = append(sorted, v)
	}
	return sorted
}

func sortConcurrentIntoChannel(arr []int, ch chan int) {
	// recursion exit
	defer close(ch)
	if len(arr) <= 1 {
		if len(arr) == 1 {
			ch <- arr[0]
		}
		return
	}

	mid := len(arr)/2
	s1 := make(chan int, mid)
	s2 := make(chan int, len(arr) - mid)

	go sortConcurrentIntoChannel(arr[:mid], s1)
	go sortConcurrentIntoChannel(arr[mid:], s2)
	mergeConcurrent(s1, s2, ch)
}

func mergeConcurrent(s1, s2, ch chan int) {
	// v, ok = <- s; receiving value from channel, ok returns false when there is no more elements in channel s
	v1, ok1 := <- s1
	v2, ok2 := <- s2

	for ok1 && ok2 {
		if v1 < v2 {
			updateConcurrent(s1, ch, &v1, &ok1)
		} else {
			updateConcurrent(s2, ch, &v2, &ok2)
		}
	}

	for ok1 {
		updateConcurrent(s1, ch, &v1, &ok1)
	}

	for ok2 {
		updateConcurrent(s2, ch, &v2, &ok2)
	}
}

func updateConcurrent(s chan int, ch chan int, v *int, ok *bool) {
	ch <- *v
	*v, *ok = <- s
}

mergesort_concurrent_bench_test.go

package mergesort

import (
	"testing"
)

func BenchmarkConcurrentMergeSort_20(b *testing.B) {
	sample := generateRandomArrayInt(20, 100)
	benchmarkConcurrentSort(sample, b)
}

func BenchmarkConcurrentMergeSort_50(b *testing.B) {
	sample := generateRandomArrayInt(50, 100)
	benchmarkConcurrentSort(sample, b)
}

func BenchmarkConcurrentMergeSort_80(b *testing.B) {
	sample := generateRandomArrayInt(80, 300)
	benchmarkConcurrentSort(sample, b)
}

func BenchmarkConcurrentMergeSort_200(b *testing.B) {
	sample := generateRandomArrayInt(200, 500)
	benchmarkConcurrentSort(sample, b)
}

func BenchmarkConcurrentMergeSort_500(b *testing.B) {
	sample := generateRandomArrayInt(500, 1000)
	benchmarkConcurrentSort(sample, b)
}

func BenchmarkConcurrentMergeSort_5000(b *testing.B) {
	sample := generateRandomArrayInt(5000, 10000)
	benchmarkConcurrentSort(sample, b)
}

func BenchmarkConcurrentMergeSort_100000(b *testing.B) {
	sample := generateRandomArrayInt(100000, 400000)
	benchmarkConcurrentSort(sample, b)
}

func benchmarkConcurrentSort(sample []int, b *testing.B) {
	for n := 0; n < b.N; n++ {
		SortConcurrent(sample)
	}
}

func generateRandomArrayInt(size int, limit int) []int {
	var sample []int
	seed := rand.NewSource(time.Now().UnixNano())
	rnd := rand.New(seed)
	for i := 0; i < size; i++ {
		sample = append(sample, rnd.Intn(limit))
	}
	return sample
}

mergesort_synchronous.go

package mergesort

// This is the normal merge sort with sequential flow of steps.

func Sort(arr []int) []int {
	// recursion exit
	if len(arr) <= 1 {
		return arr
	}
	// split the arrays into half
	mid := len(arr) / 2
	// recursively split the halves into further halves, till there is only 1 element in the array.
	// putting them on the stack while splitting
	s1 := Sort(arr[:mid])
	s2 := Sort(arr[mid:])
	// recursively merge all the split arrays
	return merge(s1, s2)
}

func merge(arr1 []int, arr2 []int) []int {
	size1 := len(arr1)
	size2 := len(arr2)

	finalArr := make([]int, size1+size2)
	i := 0
	j := 0
	index := 0

	for i < size1 && j < size2 {
		if arr1[i] < arr2[j] {
			update(finalArr, arr1, &index, &i)
		} else {
			update(finalArr, arr2, &index, &j)
		}
	}
	for i < size1 {
		update(finalArr, arr1, &index, &i)
	}
	for j < size2 {
		update(finalArr, arr2, &index, &j)
	}
	return finalArr
}

func update(finalArr []int, arr []int, index *int, incrementIndex *int) {
	finalArr[*index] = arr[*incrementIndex]
	*incrementIndex++
	*index++
}

mergesort_synchronous_bench_test.go

package mergesort

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

func BenchmarkStdMergeSort_20(b *testing.B) {
	sample := generateRandomArrayInt(20, 100)
	//b.Logf("benchmarking standard merge sort with size: %d", len(sample))
	benchmarkSort(sample, b)
}

func BenchmarkStdMergeSort_50(b *testing.B) {
	sample := generateRandomArrayInt(50, 100)
	//b.Logf("benchmarking standard merge sort with size: %d", len(sample))
	benchmarkSort(sample, b)
}

func BenchmarkStdMergeSort_80(b *testing.B) {
	sample := generateRandomArrayInt(80, 300)
	//b.Logf("benchmarking standard merge sort with size: %d", len(sample))
	benchmarkSort(sample, b)
}

func BenchmarkStdMergeSort_200(b *testing.B) {
	sample := generateRandomArrayInt(200, 500)
	//b.Logf("benchmarking standard merge sort with size: %d", len(sample))
	benchmarkSort(sample, b)
}

func BenchmarkStdMergeSort_500(b *testing.B) {
	sample := generateRandomArrayInt(500, 1000)
	//b.Logf("benchmarking standard merge sort with size: %d", len(sample))
	benchmarkSort(sample, b)
}

func BenchmarkStdMergeSort_5000(b *testing.B) {
	sample := generateRandomArrayInt(5000, 10000)
	//b.Logf("benchmarking standard merge sort with size: %d", len(sample))
	benchmarkSort(sample, b)
}

func BenchmarkStdMergeSort_100000(b *testing.B) {
	sample := generateRandomArrayInt(100000, 400000)
	//b.Logf("benchmarking standard merge sort with size: %d", len(sample))
	benchmarkSort(sample, b)
}

func generateRandomArrayInt(size int, limit int) []int {
	var sample []int
	seed := rand.NewSource(time.Now().UnixNano())
	rnd := rand.New(seed)
	for i := 0; i < size; i++ {
		sample = append(sample, rnd.Intn(limit))
	}
	return sample
}

func benchmarkSort(sample []int, b *testing.B) {
	for n := 0; n < b.N; n++ {
		Sort(sample)
	}
}