also have bottom-up merge sort

4 files changed, 141 insertions, 0 deletions

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/sort_test.go b/sort/sort_test.go
index 59e0226..8415d7d 100644
--- a/sort/sort_test.go
+++ b/sort/sort_test.go
@@ -37,6 +37,23 @@ 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 TestShuffleSort(t *testing.T) {
@@ -69,6 +86,18 @@ func BenchmarkMergeSort(b *testing.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 BenchmarkShuffleSort(b *testing.B) {
 	for i := 1; i <= maxLength; i *= 10 {
 		benchmark(Shuffle, i, b)