merge_sort

# Merge sort

1. define the function `length l` that computes the length of the list `l`

`length : 'a list -> int`

2. define the function `split n l` that splits the list `l` in two sub-lists. For instance, `split 3 [2;3;5;7;9]` evaluates to `([2;3;5],[7;9])`

`split : int -> 'a list -> 'a list * 'a list`

3. define the function `merge (l1,l2)` that merges two ordered lists `l1` and `l2`. For instance, `merge ([1;5;7],[2;4;6;7;9])` evaluates to `[1; 2; 4; 5; 6; 7; 7; 9]`.

`merge : 'a list * 'a list -> 'a list`

4. define the function `sort l` that sorts the elements of the list `l`.

`sort : 'a list -> 'a list`

## Solution

```let rec length l = match l with
[] -> 0
| x::xl -> 1 + length xl;;

let rec split n l = if n=0 then ([],l) else match l with
[] -> ([],[])
| x::xl -> let (l1,l2) = split (n-1) xl in (x::l1,l2);;

let rec merge (l1,l2) = match (l1,l2) with
([],l2) -> l2
| (l1,[]) -> l1
| (x::x1,y::y2) -> if (x<y) then x::merge(x1,l2) else y::merge(l1,y2);;

let rec sort l = match l with
[] -> []
| [x] -> [x]
| _ -> let (l1,l2) = (split ((length l) / 2) l) in merge (sort l1,sort l2);;```