actually add shell sort

1 files changed, 32 insertions, 0 deletions

diff --git a/sort/shell.go b/sort/shell.go
new file mode 100644
index 0000000..99aaf3d
--- /dev/null
+++ b/sort/shell.go
@@ -0,0 +1,32 @@
+package sort
+
+import (
+	"algorithms/ds"
+)
+
+func Shell(a []ds.Comparer) []ds.Comparer {
+	length := len(a)
+	// h-sort the array
+	h := 1
+
+	for h < length/3 {
+		// 1, 4, 13, 40, 121, 364, 1093...
+		h = 3*h + 1
+	}
+
+	for h >= 1 {
+		for i := h; i < length; i++ {
+			for j := i; j >= h; j -= h {
+				if a[j].LowerThan(a[j-h]) {
+					tmp := a[j]
+					a[j] = a[j-h]
+					a[j-h] = tmp
+				}
+			}
+		}
+
+		h /= 3
+	}
+
+	return a
+}