User Tools

Site Tools


merge_sort

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

merge_sort [2015/10/08 15:20] (current)
Line 1: Line 1:
 +====== Merge sort ======
  
 +1. define the function ''​length l''​ that computes the length of the list ''​l''​
 +<code ocaml>
 +length : 'a list -> int
 +</​code>​
 +
 +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])''​
 +<code ocaml>
 +split : int -> 'a list -> 'a list * 'a list
 +</​code>​
 +
 +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]''​.
 +<code ocaml>
 +merge : 'a list * 'a list -> 'a list
 +</​code>​
 +
 +4. define the function ''​sort l''​ that sorts the elements of the list ''​l''​.
 +<code ocaml>
 +sort : 'a list -> 'a list
 +</​code>​
 +
 +===== Solution =====
 +
 +<code ocaml>
 +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);;
 +</​code>​
merge_sort.txt ยท Last modified: 2015/10/08 15:20 (external edit)