blob: bbb8de6bae171b8c705e8ab25acab1c19cb7b11e (
plain) (
blame)
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
|
let rec split (alist : int list) =
match alist with
[] -> ([], [])
| [a] -> ([a], [])
| a::b::cs ->
let (m,n) = split cs in
(a::m, b::m) ;;
let rec merge (alist : int list) (blist : int list) =
match alist with
[] -> blist
| x::xs ->
match blist with
[] -> x::xs
| y::ys ->
if x<y then x::(merge xs (y::ys))
else y::(merge (x::xs) ys) ;;
let rec msort (alist : int list) =
match alist with
[] -> []
| a::[] -> [a]
| a::b::[] -> if a<b then [a;b] else [b;a]
| xs ->
let (m,n) = split xs
in merge (msort m) (msort n) ;;
let rec mkRandList n =
match n with
0 -> []
| n -> (Random.int 10000)::(mkRandList (n-1)) ;;
let rec validation alist =
let rec validation_cons x blist =
match blist with
[] -> true
| y::ys -> if x<=y then (validation_cons y ys) else false
in
match alist with
[] -> true
| x::xs -> validation_cons x xs;;
let main = validation (msort (mkRandList 800000));;
(*
Fatal error: exception Stack_overflow
*)
|
