implement a merge sort

1 files changed, 85 insertions, 0 deletions

diff --git a/exercises/2.3-2/merge_sort_test.go b/exercises/2.3-2/merge_sort_test.go
new file mode 100644
index 0000000..95f5307
--- /dev/null
+++ b/exercises/2.3-2/merge_sort_test.go
@@ -0,0 +1,85 @@
+package main
+
+import (
+	"fmt"
+	"reflect"
+	"testing"
+)
+
+func Merge(left []int, right []int) []int {
+	total := len(left) + len(right)
+	items := []int{}
+
+	for i := 0; i < total; i++ {
+		if len(left) == 0 || len(right) == 0 {
+			break
+		}
+		if left[0] < right[0] {
+			items, left = append(items, left[0]), left[1:]
+		} else {
+			items, right = append(items, right[0]), right[1:]
+		}
+	}
+	for _, item := range left {
+		items = append(items, item)
+	}
+	for _, item := range right {
+		items = append(items, item)
+	}
+	return items
+}
+
+func MergeSort(A []int) []int {
+	length := len(A)
+
+	if length <= 1 {
+		return A
+	}
+
+	mid := length / 2
+	left := MergeSort(A[0:mid])
+	right := MergeSort(A[mid:])
+	return Merge(left, right)
+}
+
+func TestMergeSort(t *testing.T) {
+	table := []struct {
+		in  []int
+		out []int
+	}{
+		{
+			in:  []int{3},
+			out: []int{3},
+		},
+		{
+			in:  []int{3, 41},
+			out: []int{3, 41},
+		},
+		{
+			in:  []int{41, 3},
+			out: []int{3, 41},
+		},
+		{
+			in:  []int{3, 3},
+			out: []int{3, 3},
+		},
+		{
+			in:  []int{3, 41, 9},
+			out: []int{3, 9, 41},
+		},
+		{
+			in:  []int{3, 41, 52, 26, 38, 57, 9, 49},
+			out: []int{3, 9, 26, 38, 41, 49, 52, 57},
+		},
+	}
+
+	for _, test := range table {
+		t.Run(fmt.Sprintf("Sort %v", test.in), func(t *testing.T) {
+			results := MergeSort(test.in)
+
+			if !reflect.DeepEqual(results, test.out) {
+				t.Errorf("Expected: %v, Got: %v", test.out, test.in)
+			}
+		})
+	}
+}