Sorting (Merge Sort vs Insertion Sort)

sort.go

package sort

func mergeSort(arr []int) (c []int) {
	sz := len(arr)
	if sz <= 1 {
		return arr
	}
	s := int(sz / 2)
	a, b := arr[:s], arr[s:]
	la, lb := len(a), len(b)
	if la > 1 || lb > 1 {
		a = mergeSort(a)
		b = mergeSort(b)
	} else {
		c = make([]int, la+lb)
		for i, j, k := 0, 0, 0; k < la+lb; k++ {
			if i < la && j < lb {
				if a[i] < b[j] {
					c[k] = a[i]
					i++
				} else if b[j] < a[i] {
					c[k] = b[j]
					j++
				} else {
					c[k] = b[j]
					c[k+1] = a[i]
					k++
					i++
					j++
				}
			} else if i < la && j >= lb {
				c[k] = a[i]
				i++
			} else {
				c[k] = b[j]
				j++
			}
		}
	}
	return
}

func insertionSort(arr []int) []int {
	for i := 1; i < len(arr); i++ {
		x := arr[i]
		j := i - 1
		for j >= 0 && arr[j] > x {
			arr[j+1] = arr[j]
			j--
		}
		arr[j+1] = x
	}
	return arr
}

sort_test.go

package sort

import (
	"flag"
	"math/rand"
	"os"
	"testing"
)

var (
	smallArr  = []int{}
	mediumArr = []int{}
	largeArr  = []int{}
)

func TestInsertionSortEven(t *testing.T) {
	arr := []int{5, 8, 2, 4, 1, 7, 6, 3}
	expected := []int{1, 2, 3, 4, 5, 6, 7, 8}
	arr = insertionSort(arr)
	t.Logf("arr = %v", arr)
	for i := 0; i < len(arr); i++ {
		if arr[i] != expected[i] {
			t.Errorf("Expected %v, actual %v", expected, arr)
		}
	}
}

func TestMergeSortEven(t *testing.T) {
	arr := []int{5, 8, 2, 4, 1, 7, 6, 3}
	expected := []int{1, 2, 3, 4, 5, 6, 7, 8}
	arr = mergeSort(arr)
	t.Logf("arr = %v", arr)
	for i := 0; i < len(arr); i++ {
		if arr[i] != expected[i] {
			t.Errorf("Expected %v, actual %v", expected, arr)
		}
	}
}

func TestInsertionSortOdd(t *testing.T) {
	arr := []int{5, 8, 2, 4, 1, 9, 7, 6, 3}
	expected := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
	arr = insertionSort(arr)
	t.Logf("arr = %v", arr)
	for i := 0; i < len(arr); i++ {
		if arr[i] != expected[i] {
			t.Errorf("Expected %v, actual %v", expected, arr)
		}
	}
}

func TestMergeSortOdd(t *testing.T) {
	arr := []int{5, 8, 2, 4, 1, 9, 7, 6, 3}
	expected := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
	arr = mergeSort(arr)
	t.Logf("arr = %v", arr)
	for i := 0; i < len(arr); i++ {
		if arr[i] != expected[i] {
			t.Errorf("Expected %v, actual %v", expected, arr)
		}
	}
}

func TestMain(m *testing.M) {
	flag.Parse()
	if !testing.Short() {
		for i := 0; i < 10000; i++ {
			smallArr = append(smallArr, rand.Intn(9999))
		}
		for i := 0; i < 100000; i++ {
			mediumArr = append(mediumArr, rand.Intn(9999))
		}
		for i := 0; i < 500000; i++ {
			largeArr = append(largeArr, rand.Intn(9999))
		}
	}
	os.Exit(m.Run())
}

func BenchmarkSmallMS(b *testing.B) {
	for i := 0; i < b.N; i++ {
		mergeSort(smallArr)
	}
}

func BenchmarkSmallIS(b *testing.B) {
	for i := 0; i < b.N; i++ {
		insertionSort(smallArr)
	}
}

func BenchmarkMediumMS(b *testing.B) {
	for i := 0; i < b.N; i++ {
		mergeSort(mediumArr)
	}
}

func BenchmarkMediumIS(b *testing.B) {
	for i := 0; i < b.N; i++ {
		insertionSort(mediumArr)
	}
}

func BenchmarkLargeMS(b *testing.B) {
	for i := 0; i < b.N; i++ {
		mergeSort(largeArr)
	}
}

func BenchmarkLargeIS(b *testing.B) {
	for i := 0; i < b.N; i++ {
		insertionSort(largeArr)
	}
}

So I updated this to be a package w/ tests and benchmarking. Optimized the merge sort to not use append (which was a performance bottleneck)

Results of benchmark:

BenchmarkSmallMS-4        100000             19883 ns/op                                                                                                                                                            
BenchmarkSmallIS-4       5000000               239 ns/op                                                                                                                                                            
BenchmarkMediumMS-4        10000            213685 ns/op                                                                                                                                                            
BenchmarkMediumIS-4      1000000              2287 ns/op                                                                                                                                                            
BenchmarkLargeMS-4          1000           1294538 ns/op                                                                                                                                                            
BenchmarkLargeIS-4        100000             11915 ns/op   

I find it kind of interesting that even at 5,000 numbers, insertion sort benchmarks faster still.

So I optimized a bit more. The additional call did not help the run time at all.
I also made the data sets larger, and now you can clearly see the benefit of merge sort over insertion sort.
Small = 10k
Medium = 100k
Large = 500k

PASS                                                                                                                                                                                                                
BenchmarkSmallMS-4          2000            644072 ns/op                                                                                                                                                            
BenchmarkSmallIS-4        100000             22903 ns/op                                                                                                                                                            
BenchmarkMediumMS-4          200           6790029 ns/op                                                                                                                                                            
BenchmarkMediumIS-4            1        4980277100 ns/op                                                                                                                                                            
BenchmarkLargeMS-4            50          29980420 ns/op                                                                                                                                                            
BenchmarkLargeIS-4             1        127065807900 ns/op                                                                                                                                                          
ok      github.com/xorith/lessons/merge-sort    139.540s 

Quick update to exit early if there's no work to be done.

And another benchmark result:

PASS                                                                                                                                                                                                                
BenchmarkSmallMS-4          3000            481411 ns/op                                                                                                                                                            
BenchmarkSmallIS-4        100000             22081 ns/op                                                                                                                                                            
BenchmarkMediumMS-4          300           4320245 ns/op                                                                                                                                                            
BenchmarkMediumIS-4            1        4906207100 ns/op                                                                                                                                                            
BenchmarkLargeMS-4            50          26784680 ns/op                                                                                                                                                            
BenchmarkLargeIS-4             1        127993339800 ns/op                                                                                                                                                          
ok      github.com/xorith/lessons/merge-sort    139.990s  

As you can clearly see, the NS/OP for MS (merge sort) has dropped nicely. :)