From 5737e8430d43b3b5bd448f761cd2f3c35707a174 Mon Sep 17 00:00:00 2001 From: Rose Hogenson Date: Sun, 28 Apr 2024 15:06:43 -0700 Subject: Add case over int. --- sort.sml | 30 ++++++++++++++++++++++++++++++ 1 file changed, 30 insertions(+) create mode 100644 sort.sml (limited to 'sort.sml') 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 -- cgit v1.3.1