:PROPERTIES: :ID: 6409e8d1-5a47-4c95-99f3-c1a8a02ecc3f :mtime: 20231016024255 :ctime: 20231016024239 :END: #+title: mergesort #+filetags: :public:project: * Definition Mergesort is an algorithm for [[id:9c2f8198-fead-4602-aa99-8f5312e239fb][Sorting a List]]. ** Implementation of mergesort in ocaml #+BEGIN_SRC ocaml let rec merge = function | [] , ys -> ys | xs , [] -> xs | x :: xs , y :: ys -> if x <= y then x :: merge (xs , y :: ys) else y :: merge (x :: xs , ys) let rec split left right xs n = match xs with | [] -> (left , right) | y :: ys -> if n = 0 then (left , right @ xs) else split (y :: left) right ys ( n - 1 ) let rec mergesort = function | [] -> [] | [x] -> [x] | xs -> let (left , right) = split [] [] xs (List.length xs / 2) in merge (mergesort left , mergesort right) #+END_SRC #+RESULTS: : <fun> #+BEGIN_SRC ocaml :exports both mergesort [ 3 ; 4 ; 5 ; 1 ; 51 ;7 ;10 ;8 ;9 ] #+END_SRC #+RESULTS: | 1 | 3 | 4 | 5 | 7 | 8 | 9 | 10 | 51 | * [[id:43dd8110-2e8e-42a3-8d7a-55da895da68a][Asymptotic Complexity]] of Mergesort Time complexity of mergesort is $O(n \log n)$ Mergesort is optimal in terms of time complexity.