2 Domtool (http
://hcoop
.sf
.net
/)
3 Copyright (C
) 2004-2005 Adam Chlipala
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
.
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
.
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
.
20 (* Utility functions
*)
22 structure MltonUtil
:> MLTON_UTIL
=
24 fun merge (L1
: ('a
* int) list
, L2
: ('a
* int) list
) acc
=
26 (_
, []) => List.revAppend (acc
, L1
)
27 |
([], _
) => List.revAppend (acc
, L2
)
30 merge (t1
, L2
) (n1
:: acc
)
32 merge (L1
, t2
) (n2
:: acc
)
40 | h
::t
=> split (n
-1) t (h
::acc
)
48 val mid
= length L
div 2
49 val (L1
, L2
) = split mid L
[]
51 merge (mergeSort L1
, mergeSort L2
) []