1 files changed, 24 insertions, 0 deletions
diff --git a/Sort.sml b/Sort.sml
new file mode 100644
index 0000000..d9a70e9
--- /dev/null
+++ b/Sort.sml
@@ -0,0 +1,24 @@
+signature SORT =
+sig
+  val sort : ('a * 'a -> order) -> 'a list -> 'a list
+end
+
+structure Sort :> SORT =
+struct
+  fun merge (_ : 'a * 'a -> order) ([] : 'a list) (l2 : 'a list) : 'a list = l2
+    | merge _ l1 [] = l1
+    | merge cmp (xl as x :: xs) (yl as y :: ys) =
+        (case cmp (x, y) of
+          GREATER => y :: merge cmp xl ys
+        | _ => x :: merge cmp xs yl)
+
+  fun sort (_ : 'a * 'a -> order) ([] : 'a list) : 'a list = []
+    | sort _ [x] = [x]
+    | sort cmp l =
+        let
+          val n = length l
+          val half1 = List.take (l, n div 2)
+          val half2 = List.drop (l, n div 2)
+        in merge cmp (sort cmp half1) (sort cmp half2)
+        end
+end