Commit | Line | Data |
---|---|---|
42a86d96 AC |
1 | (* |
2 | Domtool (http://hcoop.sf.net/) | |
3 | Copyright (C) 2004-2005 Adam Chlipala | |
4 | ||
5 | This program is free software; you can redistribute it and/or | |
6 | modify it under the terms of the GNU General Public License | |
7 | as published by the Free Software Foundation; either version 2 | |
8 | of the License, or (at your option) any later version. | |
9 | ||
10 | This program is distributed in the hope that it will be useful, | |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
13 | GNU General Public License for more details. | |
14 | ||
15 | You should have received a copy of the GNU General Public License | |
16 | along with this program; if not, write to the Free Software | |
17 | Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. | |
18 | *) | |
19 | ||
20 | (* Utility functions *) | |
21 | ||
22 | structure MltonUtil :> MLTON_UTIL = | |
23 | struct | |
24 | fun merge (L1 : ('a * int) list, L2 : ('a * int) list) acc = | |
25 | case (L1, L2) of | |
26 | (_, []) => List.revAppend (acc, L1) | |
27 | | ([], _) => List.revAppend (acc, L2) | |
28 | | (n1::t1, n2::t2) => | |
29 | if #2 n1 > #2 n2 then | |
30 | merge (t1, L2) (n1 :: acc) | |
31 | else | |
32 | merge (L1, t2) (n2 :: acc) | |
33 | ||
34 | fun split n L acc = | |
35 | if n <= 0 then | |
36 | (acc, L) | |
37 | else | |
38 | case L of | |
39 | [] => (acc, []) | |
40 | | h::t => split (n-1) t (h::acc) | |
41 | ||
42 | fun mergeSort L = | |
43 | case L of | |
44 | [] => L | |
45 | | [a] => L | |
46 | | _ => | |
47 | let | |
48 | val mid = length L div 2 | |
49 | val (L1, L2) = split mid L [] | |
50 | in | |
51 | merge (mergeSort L1, mergeSort L2) [] | |
52 | end | |
53 | end | |
54 |