From de286db8594d547591ff765f4d5934d99248779b Mon Sep 17 00:00:00 2001
From: Paul Buetow <paul@buetow.org>
Date: Tue, 21 Jul 2020 20:41:37 +0100
Subject: merge sort works

---
 ds/arraylist.go   |  6 ++++++
 ds/integer.go     | 16 ++++++++--------
 sort/insertion.go |  4 +---
 sort/sort_test.go | 12 ++++++++++++
 4 files changed, 27 insertions(+), 11 deletions(-)

diff --git a/ds/arraylist.go b/ds/arraylist.go
index c2ada86..7bc002a 100644
--- a/ds/arraylist.go
+++ b/ds/arraylist.go
@@ -35,3 +35,9 @@ func (a ArrayList) Sorted() bool {
 	}
 	return true
 }
+
+func (a ArrayList) SwapPos(i, j int) {
+	tmp := a[i]
+	a[i] = a[j]
+	a[j] = tmp
+}
diff --git a/ds/integer.go b/ds/integer.go
index bd7dbe2..4abb349 100644
--- a/ds/integer.go
+++ b/ds/integer.go
@@ -6,7 +6,7 @@ import (
 )
 
 type Integer struct {
-	val int
+	Val int
 }
 
 func RandomIntegers(length, max int) ArrayList {
@@ -36,29 +36,29 @@ func ReverseSortedIntegers(length int) ArrayList {
 }
 
 func (i Integer) String() string {
-	return fmt.Sprintf("%d", i.val)
+	return fmt.Sprintf("%d", i.Val)
 }
 
 func (i Integer) Int() int {
-	return i.val
+	return i.Val
 }
 
 func (i Integer) Equal(j Elem) bool {
-	return i.val == j.Int()
+	return i.Val == j.Int()
 }
 
 func (i Integer) Lower(j Elem) bool {
-	return i.val < j.Int()
+	return i.Val < j.Int()
 }
 
 func (i Integer) LowerEqual(j Elem) bool {
-	return i.val <= j.Int()
+	return i.Val <= j.Int()
 }
 
 func (i Integer) Higher(j Elem) bool {
-	return i.val > j.Int()
+	return i.Val > j.Int()
 }
 
 func (i Integer) HigherEqual(j Elem) bool {
-	return i.val >= j.Int()
+	return i.Val >= j.Int()
 }
diff --git a/sort/insertion.go b/sort/insertion.go
index 465e8b4..9f7215b 100644
--- a/sort/insertion.go
+++ b/sort/insertion.go
@@ -12,9 +12,7 @@ func Insertion(a ds.ArrayList) ds.ArrayList {
 			if a[j].Higher(a[j-1]) {
 				break
 			}
-			tmp := a[j]
-			a[j] = a[j-1]
-			a[j-1] = tmp
+			a.SwapPos(j, j-1)
 		}
 	}
 
diff --git a/sort/sort_test.go b/sort/sort_test.go
index ad75fff..59e0226 100644
--- a/sort/sort_test.go
+++ b/sort/sort_test.go
@@ -33,6 +33,12 @@ func TestShellSort(t *testing.T) {
 	}
 }
 
+func TestMergeSort(t *testing.T) {
+	for i := 1; i <= maxLength; i *= 10 {
+		test(Merge, i, t)
+	}
+}
+
 func TestShuffleSort(t *testing.T) {
 	for i := 10; i <= maxLength; i *= 10 {
 		testShuffle(Shuffle, i, t)
@@ -57,6 +63,12 @@ func BenchmarkShellSort(b *testing.B) {
 	}
 }
 
+func BenchmarkMergeSort(b *testing.B) {
+	for i := 1; i <= maxLength; i *= 10 {
+		benchmark(Merge, i, b)
+	}
+}
+
 func BenchmarkShuffleSort(b *testing.B) {
 	for i := 1; i <= maxLength; i *= 10 {
 		benchmark(Shuffle, i, b)
-- 
cgit v1.2.3