1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
(* https://stackoverflow.com/questions/25839939/understanding-merge-sort-in-ml *)
fun split [] = ([], [])
| split [a] = ([a], [])
| split (a::b::cs) =
let
val (m,n) = split cs
in
(a::m, b::n)
end;
fun merge ([], ys) = ys
| merge (xs, []) = xs
| merge (x::xs, y::ys) =
if x<y then
x::merge(xs, y::ys)
else
y::merge(x::xs, ys);
fun msort [] = []
| msort [a] = [a]
| msort [a,b] = if a<b then [a,b] else [b,a]
| msort xs =
let
val (m,n) = split xs;
in
merge (msort m, msort n)
end;
(* Creates a random list *)
local
val nextInt = Random.randRange(1,10000);
val r = Random.rand(1,1);
in
fun mkRandList 0 = []
| mkRandList n = (nextInt r)::(mkRandList (n-1))
end;
(* Validation checks *)
fun validation [] = true
| validation (x::xs) =
let fun validation_cons x [] = true
| validation_cons x (y::ys) =
if x<=y then validation_cons y ys
else false
in
validation_cons x xs
end;
(* Main *)
msort (mkRandList 800000);
|
