6 files changed, 154 insertions, 6 deletions

diff --git a/sort/insertion.go b/sort/insertion.go
index 465e8b4..3e271b0 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.Swap(j, j-1)
 		}
 	}
 
diff --git a/sort/merge.go b/sort/merge.go
new file mode 100644
index 0000000..e57ea6d
--- /dev/null
+++ b/sort/merge.go
@@ -0,0 +1,49 @@
+package sort
+
+import (
+	"algorithms/ds"
+)
+
+func Merge(a ds.ArrayList) ds.ArrayList {
+	aux := make(ds.ArrayList, len(a))
+	mergeSort(a, aux, 0, len(a)-1)
+
+	return a
+}
+
+func mergeSort(a, aux ds.ArrayList, lo, hi int) {
+	if lo >= hi {
+		return
+	}
+	mid := lo + (hi-lo)/2
+
+	mergeSort(a, aux, lo, mid)
+	mergeSort(a, aux, mid+1, hi)
+	merge(a, aux, lo, mid, hi)
+}
+
+func merge(a, aux ds.ArrayList, lo, mid, hi int) {
+	for i := lo; i <= hi; i++ {
+		aux[i] = a[i]
+	}
+
+	i := lo
+	j := mid + 1
+
+	for k := lo; k <= hi; k++ {
+		switch {
+		case i > mid:
+			a[k] = aux[j]
+			j++
+		case j > hi:
+			a[k] = aux[i]
+			i++
+		case aux[i].Higher(aux[j]):
+			a[k] = aux[j]
+			j++
+		default:
+			a[k] = aux[i]
+			i++
+		}
+	}
+}
diff --git a/sort/merge2.go b/sort/merge2.go
new file mode 100644
index 0000000..774c3c5
--- /dev/null
+++ b/sort/merge2.go
@@ -0,0 +1,37 @@
+package sort
+
+import (
+	"algorithms/ds"
+	"sync"
+)
+
+// Merge2 is a parallelized version of Merge
+func Merge2(a ds.ArrayList) ds.ArrayList {
+	aux := make(ds.ArrayList, len(a))
+	mergeSort2(a, aux, 0, len(a)-1)
+
+	return a
+}
+
+func mergeSort2(a, aux ds.ArrayList, lo, hi int) {
+	mid := lo + (hi-lo)/2
+	defer merge(a, aux, lo, mid, hi)
+
+	if hi-lo <= 1000 {
+		mergeSort(a, aux, lo, mid)
+		mergeSort(a, aux, mid+1, hi)
+		return
+	}
+
+	var wg sync.WaitGroup
+	wg.Add(2)
+	go func() {
+		mergeSort2(a, aux, lo, mid)
+		wg.Done()
+	}()
+	go func() {
+		mergeSort2(a, aux, mid+1, hi)
+		wg.Done()
+	}()
+	wg.Wait()
+}
diff --git a/sort/merge3.go b/sort/merge3.go
new file mode 100644
index 0000000..fbc1650
--- /dev/null
+++ b/sort/merge3.go
@@ -0,0 +1,26 @@
+package sort
+
+import (
+	"algorithms/ds"
+)
+
+// Merge3 is the bottom up version of merge sort.
+func Merge3(a ds.ArrayList) ds.ArrayList {
+	length := len(a)
+	aux := make(ds.ArrayList, length)
+
+	for sz := 1; sz < length; sz = sz + sz {
+		for lo := 0; lo < length-sz; lo += sz + sz {
+			merge(a, aux, lo, lo+sz-1, min(lo+sz+sz-1, length-1))
+		}
+	}
+
+	return a
+}
+
+func min(a, b int) int {
+	if a <= b {
+		return a
+	}
+	return b
+}
diff --git a/sort/shuffle.go b/sort/shuffle.go
index 9c6f5b9..26db8c4 100644
--- a/sort/shuffle.go
+++ b/sort/shuffle.go
@@ -10,9 +10,6 @@ func Shuffle(a ds.ArrayList) ds.ArrayList {
 
 	for i := 0; i < length; i++ {
 		r := length - rand.Intn(length-i) - 1
-		if r == i {
-			continue
-		}
 		tmp := a[i]
 		a[i] = a[r]
 		a[r] = tmp
diff --git a/sort/sort_test.go b/sort/sort_test.go
index bd9db9b..a0e4729 100644
--- a/sort/sort_test.go
+++ b/sort/sort_test.go
@@ -33,6 +33,29 @@ func TestShellSort(t *testing.T) {
 	}
 }
 
+func TestMergeSort(t *testing.T) {
+	for i := 1; i <= maxLength; i *= 10 {
+		test(Merge, i, t)
+	}
+	test(Merge, maxLength*2, t)
+}
+
+func TestMerge2Sort(t *testing.T) {
+	t.Log("Parallel merge sort")
+	for i := 1; i <= maxLength; i *= 10 {
+		test(Merge2, i, t)
+	}
+	test(Merge2, maxLength*2, t)
+}
+
+func TestMerge3Sort(t *testing.T) {
+	t.Log("Bottom-up merge sort")
+	for i := 1; i <= maxLength; i *= 10 {
+		test(Merge3, i, t)
+	}
+	test(Merge3, maxLength*2, t)
+}
+
 func TestQuickSort(t *testing.T) {
 	for i := 1; i <= maxLength; i *= 10 {
 		test(Quick, i, t)
@@ -63,6 +86,24 @@ func BenchmarkShellSort(b *testing.B) {
 	}
 }
 
+func BenchmarkMergeSort(b *testing.B) {
+	for i := 1; i <= maxLength; i *= 10 {
+		benchmark(Merge, i, b)
+	}
+}
+
+func BenchmarkMerge2Sort(b *testing.B) {
+	for i := 1; i <= maxLength; i *= 10 {
+		benchmark(Merge2, i, b)
+	}
+}
+
+func BenchmarkMerge3Sort(b *testing.B) {
+	for i := 1; i <= maxLength; i *= 10 {
+		benchmark(Merge3, i, b)
+	}
+}
+
 func BenchmarkQuickSort(b *testing.B) {
 	for i := 1; i <= maxLength; i *= 10 {
 		benchmark(Quick, i, b)