:PROPERTIES: :ID: 13b99e2c-1873-48f9-906b-f4e5f2015a0e :mtime: 20231023022406 20231016021415 :ctime: 20231016021357 :END: #+title: insertion sort #+filetags: :public:project: * Definition Insertion sort is an algorithm which is designed to [[id:9c2f8198-fead-4602-aa99-8f5312e239fb][Sorting a List]]. * How does the algorithm work? ** In [[id:8952459c-5076-4e68-8a68-5f658209f39e][OCAML]] "insert" inserts an element into its correct position. #+BEGIN_SRC ocaml let rec insert x = function | [] -> [x] | y :: ys -> if x <= y then x :: y :: ys else y :: insert x ys #+END_SRC #+RESULTS: : <fun> "insertion_sort" repeatedly inserts each element. #+BEGIN_SRC ocaml let rec insertion_sort = function | [] -> [] | x :: xs -> insert x (insertion_sort xs) let insertion_sort2 = List.fold_left (Fun.flip insert) [] #+END_SRC #+RESULTS: : <fun> #+BEGIN_SRC ocaml :exports both insertion_sort [3 ; 4; 1 ; 2 ; 3 ;123 ; 1] #+END_SRC #+RESULTS: | 1 | 1 | 2 | 3 | 3 | 4 | 123 | #+BEGIN_SRC ocaml :exports both insertion_sort2 [3 ; 4; 1 ; 2 ; 3 ;123 ; 1] #+END_SRC #+RESULTS: | 1 | 1 | 2 | 3 | 3 | 4 | 123 | *** Stack Trace of Insertion Sort #+BEGIN_SRC ocaml let insertion_sort2 [2 ; 3 ; 1] = List.fold_left (Fun.flip insert) [] [2 ; 3 ; 1] = Fun.flip insert [] 2 (List.fold_left (Fun.flip insert) [] [3 ; 1]) = insert 2 (List.fold_left (Fun.flip insert) [] [3 ; 1]) = insert 2 (insert 3 (List.fold_left (Fun.flip insert) [] [ 1])) = insert 2 (insert 3 ( insert 1 [])) = insert 2 (insert 3 [1]) = insert 2 [1 ; 3] = [1 ; 2 ; 3] #+END_SRC * [[id:43dd8110-2e8e-42a3-8d7a-55da895da68a][Asymtotic Complexity]] of Insertion Sort Time complexity is $O(n^{2})$ The worst case for insertion sort is when the list is reversed sorted. The best case for insertion sort is when the list is already sorted.