Merge pull request #1 from MatrixWood/dev

CanftIn · web-flow · commit bb350d1f66b0 · 2020-03-16T17:05:33.000+08:00
update merge sort
diff --git a/algorithm.ml b/algorithm.ml
@@ -1,14 +1,21 @@
-(* factorial : int -> int *)
+(*
+   val factorial : int -> int = <fun>
+   val length : 'a list -> int = <fun>
+   val take : int -> 'a list -> 'a list = <fun>
+   val drop : int -> 'a list -> 'a list = <fun>
+   val sort_insert : 'a -> 'a list -> 'a list = <fun>
+   val sort : 'a list -> 'a list = <fun>
+   val merge : ('a -> 'a -> bool) -> 'a list -> 'a list -> 'a list = <fun>
+   val split : 'a list -> 'a list -> 'a list -> 'a list * 'a list = <fun>
+   val mergesort : ('a -> 'a -> bool) -> 'a list -> 'a list = <fun>
+   val map : ('a -> 'b) -> 'a list -> 'b list = <fun>
+
+*)
 let rec factorial a =
   match a with
   | 1 -> 1
   | _ -> a * factorial (a - 1)
 
-(* isvowel : int -> int *)
-let rec isvowel c =
-  c = 'a' || c = 'e' || c = 'i' || c = 'o' || c = 'u'
-
-
 let rec length l =
   match l with
   | [] -> 0
@@ -41,3 +48,27 @@ let rec sort l =
   | [] -> []
   | h :: t -> sort_insert h (sort t)
 
+let rec merge cmp x y =
+  match (x, y) with
+  | ([], _) -> y
+  | (_, []) -> x
+  | (h1 :: t1, h2 :: t2) ->
+    if cmp h2 h1
+    then h1 :: (merge cmp t1 y)
+    else h2 :: (merge cmp x t2)
+
+and split x y z =
+  match x with
+  | [] -> (y, z)
+  | x :: resto -> split resto z (x :: y)
+
+and mergesort cmp x =
+  match x with
+  | ([] | _ :: []) -> x
+  | _ -> let (pri, seg) = split x [] []
+    in (merge cmp (mergesort cmp pri) (mergesort cmp seg))
+
+let rec map f l =
+  match l with
+  | [] -> []
+  | h::t -> f h :: map f t
