Add a recursive implementation of Insertion Sort

jbranchaud · jbranchaud · commit 520665b5e65a · 2018-07-24T19:36:30.000-05:00
diff --git a/src/Index.re b/src/Index.re
@@ -13,4 +13,7 @@ Invariant.expect(Array.of_list(expected_list) == sorted_array);
 
 let sorted_list_2 = SelectionSort.sort(unsorted_list);
 
-Invariant.expect(sorted_list_2 == expected_list);
+Invariant.expect(sorted_list_2 == expected_list);
+
+let sorted_list_3 = RecursiveInsertionSort.sort(unsorted_list);
+Invariant.expect(sorted_list_3 == expected_list);
diff --git a/src/RecursiveInsertionSort.re b/src/RecursiveInsertionSort.re
@@ -0,0 +1,14 @@
+let rec insert_item = (items: list(int), item: int) =>
+  switch (items) {
+  | [] => [item]
+  | [head, ...rest] when item < head => [item, head, ...rest]
+  | [head, ...rest] when item > head =>
+    let sorted_rest = insert_item(rest, item);
+    [head, ...sorted_rest];
+  };
+
+let rec sort = items : list(int) =>
+  switch (items) {
+  | [] => []
+  | [head, ...rest] => insert_item(sort(rest), head)
+  };
