merge_sort

# Differences

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

 — 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''​ + + 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 [] + | [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)