Commit | Line | Data |
---|---|---|
7f918cf1 CE |
1 | (* Copyright (C) 2009 Matthew Fluet. |
2 | * Copyright (C) 1999-2006 Henry Cejtin, Matthew Fluet, Suresh | |
3 | * Jagannathan, and Stephen Weeks. | |
4 | * | |
5 | * MLton is released under a BSD-style license. | |
6 | * See the file MLton-LICENSE for details. | |
7 | *) | |
8 | ||
9 | signature MERGE_SORT = | |
10 | sig | |
11 | type 'a t | |
12 | ||
13 | (* The comparison function ('a * 'a -> bool) for any of these should | |
14 | * always be the <= funtion, not just <. | |
15 | * This is necessary to handle duplicate elements. | |
16 | *) | |
17 | val make: ('a * 'a -> bool) -> {isSorted: 'a t -> bool, | |
18 | merge: 'a t * 'a t -> 'a t, | |
19 | sort: 'a t -> 'a t} | |
20 | val isSorted: 'a t * ('a * 'a -> bool) -> 'a t | |
21 | val merge: 'a t * 'a t * ('a * 'a -> bool) -> 'a t | |
22 | val sort: 'a t * ('a * 'a -> bool) -> 'a t | |
23 | end | |
24 | ||
25 | functor TestMergeSort (S: MERGE_SORT) = | |
26 | struct | |
27 | ||
28 | open S | |
29 | ||
30 | val _ = | |
31 | Assert.assert | |
32 | ("TestMergeSort", fn () => | |
33 | let | |
34 | fun check (l: int list): bool = | |
35 | List.insertionSort (l, op <=) = toList (sort (fromList l, op <=)) | |
36 | in | |
37 | List.forall | |
38 | ([[], | |
39 | [1], | |
40 | [1,2], | |
41 | [1,2,3], | |
42 | [2,1,3], | |
43 | [1,2,3,4,5], | |
44 | [3,5,6,7,8,1,2,3,6,4]], | |
45 | check) | |
46 | end) | |
47 | ||
48 | end |