package main

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

func main() {
  benchmark(100_000)
}

// 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

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

	start = time.Now()
	mergeSort(A, func(a, b int) bool {
		return a < b
	})
	fmt.Println("elapsed for merge sort:", time.Now().Sub(start))

	start = time.Now()
	insertionMergeSort(A, func(a, b int) bool {
		return a < b
	})
	fmt.Println("elapsed for insertion merge sort:", time.Now().Sub(start))
}

// 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
}

// sort sorts the given slice by using the Merge Sort algorithm
// the algorithm uses the divide & conquer approach by dividing the problem into sub problems
// the algorithm works recursively, by calling itself
// HOW IT WORKS:
// 1. the slice is divided in 2 pieces (right, left)
// 2. the right and left sides are sorted first then they are merged
// 3. the sort function divides the incoming slice till it cannot be divided anymore (the slice has only 1 element)
// 4. after that it starts merging & sorting all the slices back
// 5. at the end we have 1 single slice sorted out
func sort(A []int, fn sortFunc) []int {
	if fn == nil {
		fn = func(a, b int) bool {
			return a < b
		}
	}
	if len(A) > 1 {
		m := len(A) / 2
		L := A[:m]
		R := A[m:]

		// The long version for languages that do not support clever constructs
		//n1 := len(A) / 2
		//n2 := len(A) - n1
		//L, R := make([]int, n1), make([]int, n2)
		//for i := 0; i < n1; i++ {
		//	L[i] = A[i]
		//}
		//for j := 0; j < n2; j++ {
		//	R[j] = A[n1+j]
		//}

		// sort the right side
		// sort the left side
		// merge the sorted sides
		// do this recursively till the slice has 1 element only
		A = merge(sort(R, fn), sort(L, fn), fn)
	}
	return A
}

// mergeSort sorts the given slice by using the Merge Sort algorithm
// the algorithm uses the divide & conquer approach by dividing the problem into sub problems
// the algorithm works recursively, by calling itself
// HOW IT WORKS:
// 1. the slice is divided in 2 pieces (right, left)
// 2. the right and left sides are sorted first then they are merged
// 3. the sort function divides the incoming slice till it cannot be divided anymore (the slice has only 1 element)
// 4. after that it starts merging & sorting all the slices back
// 5. at the end we have 1 single slice sorted out
func mergeSort(A []int, fn sortFunc) []int {
	if fn == nil {
		fn = func(a, b int) bool {
			return a < b
		}
	}
	if len(A) > 1 {
		m := len(A) / 2
		L := A[:m]
		R := A[m:]

		// The long version for languages that do not support clever constructs
		//n1 := len(A) / 2
		//n2 := len(A) - n1
		//L, R := make([]int, n1), make([]int, n2)
		//for i := 0; i < n1; i++ {
		//	L[i] = A[i]
		//}
		//for j := 0; j < n2; j++ {
		//	R[j] = A[n1+j]
		//}

		// sort the right side
		// sort the left side
		// merge the sorted sides
		// do this recursively till the slice has 1 element only
		A = merge(mergeSort(R, fn), mergeSort(L, fn), fn)
	}
	return A
}

// 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
}