From d330522b31f9a32e9549745008b596fdca9b17e5 Mon Sep 17 00:00:00 2001
From: Paul Buetow <paul@buetow.org>
Date: Sun, 26 Jul 2020 08:48:45 +0100
Subject: also have bottom-up merge sort

---
 sort/merge3.go | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)
 create mode 100644 sort/merge3.go

(limited to 'sort/merge3.go')

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
+}
-- 
cgit v1.2.3