diff options
Diffstat (limited to 'sort.sml')
| -rw-r--r-- | sort.sml | 24 |
1 files changed, 9 insertions, 15 deletions
@@ -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 |