User Tools

Site Tools


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);;
merge_sort.txt · Last modified: 2015/10/08 15:20 (external edit)