From 554a7a259f3feefb586374ac5a3b57acc99a4446 Mon Sep 17 00:00:00 2001
From: Paul Buetow <paul@buetow.org>
Date: Tue, 14 Jul 2020 08:53:17 +0100
Subject: add insertion sort

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

(limited to 'sort/insertion.go')

diff --git a/sort/insertion.go b/sort/insertion.go
new file mode 100644
index 0000000..d14c275
--- /dev/null
+++ b/sort/insertion.go
@@ -0,0 +1,22 @@
+package sort
+
+import (
+	"algorithms/ds"
+)
+
+func Insertion(a []ds.Comparer) []ds.Comparer {
+	length := len(a)
+
+	for i := 0; i < length; i++ {
+		for j := i; j > 0; j-- {
+			if a[j].HigherThan(a[j-1]) {
+				break
+			}
+			tmp := a[j]
+			a[j] = a[j-1]
+			a[j-1] = tmp
+		}
+	}
+
+	return a
+}
-- 
cgit v1.2.3