add insertion sort

1 files changed, 22 insertions, 0 deletions

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