1 files changed, 30 insertions, 0 deletions
diff --git a/sort.sml b/sort.sml
new file mode 100644
index 0000000..97e4a8b
--- /dev/null
+++ b/sort.sml
@@ -0,0 +1,30 @@
+signature SORT =
+sig
+  val sort : ('a * 'a -> order) -> 'a list -> 'a list
+end
+
+structure Sort :> SORT =
+struct
+  fun split (l : 'a list, n : int) : ('a list * int) * ('a list * int) =
+    let val h = n div 2
+    in ((l, h), (List.drop (l, h), n - h))
+    end
+
+  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' (cmp : 'a * 'a -> order) (s as (l : 'a list, n : int)) : 'a list =
+    if n < 2 then List.take (l, n) else
+    let
+      val (first, second) = split s
+      val firstSorted = sort' cmp first
+      val secondSorted = sort' cmp second
+    in merge cmp firstSorted secondSorted
+    end
+
+  fun sort (cmp : 'a * 'a -> order) (l : 'a list) : 'a list = sort' cmp (l, length l)
+end