implement a merge sort

3 files changed, 111 insertions, 2 deletions

diff --git a/README.md b/README.md
index 4f548fe..135eaaa 100644
--- a/README.md
+++ b/README.md
@@ -99,7 +99,7 @@ When you have completed this objective, you should be able to
 
 #### Required Activities
 
-* [ ] Study Section 2.3 of the textbook.
+* [X] Study Section 2.3 of the textbook.
 * [ ] Do Exercise 2.3-5 from the textbook as part of Assignment 1.
 
 ### Section 1.3: Asymptotics
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)
+			}
+		})
+	}
+}
diff --git a/notes.md b/notes.md
index dcc1a74..eb58099 100644
--- a/notes.md
+++ b/notes.md
@@ -730,7 +730,7 @@ Analysis of merge sort
 
 ```plaintext
               -----------------------
-              |3|41|52|26|38|57|9|49|
+              |3|9|26|38|41|49|52|57|
               -----------------------
                /                  \
       ------------             ------------
@@ -783,3 +783,27 @@ for k = k to r
     A[k] = R[j]
     j = j + 1
 ```
+
+2.3-3: Use mathematical induction to show that when `n` is an exact power of 2,
+the solution of the recurrence ... is `T(n) = nlg(n)`
+
+```plaintext
+         2            if n = 2
+T(n) = { 2T(n/2) + n  if n = 2**k, for k > 1
+```
+
+ ???
+
+2.3-4: We can express insertion sort as a recursive procedure as follows In
+order to sort `A[i..n]`, we recursively sort `A[i..n-1]` and then insert `A[n]`
+into the sorted array `A[1..n-1]`. Write a recurrence for the worst-case running
+time of this recursive version of insertion sort.
+
+
+2.3-5: Referring back to the searching problem (see Exercise 2.1-3), observe that
+    if the sequence A is sorted, we can check the midpoint of the sequence
+    against v and eliminate half of the sequence from further consideration. The
+    binary search algorithm repeats this procedure, halving the size of the
+    remaining portion of the sequence each time. Write pseudocode, either
+    iterative or recursive, for binary search. Argue that the worst case running
+    time of binary search is O(lg(n)).