steevehook · April 7, 2021 18:50 · Apr 7, 2021 · Apr 7, 2021 · Apr 7, 2021
diff --git a/insertion-merge-insertion_merge-sort.go b/insertion-merge-insertion_merge-sort.go
@@ -1,13 +1,13 @@
 package main
 
 import (
-  "fmt"
+	"fmt"
 	"math/rand"
 	"time"
 )
 
 func main() {
-  benchmark(100_000)
+	benchmark(100_000)
 }
 
 // Note: the more elements you are sorting the lower this number should be

diff --git a/insertion-merge-insertion_merge-sort.go b/insertion-merge-insertion_merge-sort.go
@@ -0,0 +1,200 @@
+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
+}