insertion-merge-sort.go

package main

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

func main() {
	n := 1_000_000
	var A []int
	for i := 0; i < n; i++ {
		A = append(A, rand.Intn(n))
	}
	start := time.Now()
	insertionMergeSort(A, func(a, b int) bool {
		return a < b
	})
	fmt.Println("elapsed:", time.Now().Sub(start))
}

// Note: the more elements you are sorting the lower this number should be
// the sweet spot is between: 8-20
const insertionSortMaxThreshold = 10

type sortFunc func(a, b int) bool

// insertionMergeSort uses a combination of insertion & merge sorting algorithms to sort a given slice
// it uses the insertion sorting for small data sets
// and it uses merge sort till the data set becomes small enough to use insertion sorting
func insertionMergeSort(A []int, fn sortFunc) []int {
	if fn == nil {
		fn = func(a, b int) bool {
			return a < b
		}
	}
	if len(A) > 1 {
		if len(A) <= insertionSortMaxThreshold {
			return insertionSortFunc(A, fn)
		}
		m := len(A) / 2
		L := A[:m]
		R := A[m:]

		// sort the right side
		// sort the left side
		// merge the sorted sides
		// do this recursively till the slice has a minimum of elements (i.e. 10)
		//to apply the insertion sorting algorithm
		A = merge(insertionMergeSort(R, fn), insertionMergeSort(L, fn), fn)
	}
	return A
}

// insertionSortFunc uses the insertion sort algorithm and a sorting function
func insertionSortFunc(A []int, fn sortFunc) []int {
	if fn == nil {
		fn = func(a, b int) bool {
			return a < b
		}
	}
	for j := 1; j < len(A); j++ {
		key := A[j]
		i := j - 1
		for i > -1 && fn(key, A[i]) {
			A[i+1] = A[i]
			i -= 1
		}
		A[i+1] = key
	}
	return A
}

// merge merges 2 slices into a single slice, also sorting the resulting slice
// Note: to ensure the merge function works correctly the L and R must be sorted
func merge(L, R []int, fn sortFunc) []int {
	A := make([]int, len(L)+len(R))
	i, j, k := 0, 0, 0
	// compare left & right side elements before merging
	for i < len(L) && j < len(R) {
		if fn(L[i], R[j]) {
			A[k] = L[i]
			i++
		} else {
			A[k] = R[j]
			j++
		}
		k++
	}

	// check if any elements from the left/right side
	// were missed in the comparison section above
	for i < len(L) {
		A[k] = L[i]
		i++
		k++
	}
	for j < len(R) {
		A[k] = R[j]
		j++
		k++
	}

	return A
}