also have bottom-up merge sort

1 files changed, 26 insertions, 0 deletions

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
+}