Slightly simplify the sort algorithm.

1 files changed, 9 insertions, 15 deletions

diff --git a/sort.sml b/sort.sml
index 407619f..d9a70e9 100644
--- a/sort.sml
+++ b/sort.sml
@@ -5,11 +5,6 @@ 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) =
@@ -17,14 +12,13 @@ struct
           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)
+  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