# Insertion Sort

## Introduction

Insertion sort is a simple sorting algorithm that is widely used in computer science. It works by taking one element from the unsorted list and inserting it into the correct position in the sorted list. The algorithm is efficient for small data sets but becomes inefficient for larger ones. Insertion sort can be used in situations where the data is already partially sorted or where the cost of swapping elements is high.

## Implementation

Here is an implementation of insertion sort in OCaml:

```
let rec insertion_sort = function
| [] -> []
| x :: xs -> insert x (insertion_sort xs)
and insert x = function
| [] -> [x]
| y :: ys -> if x < y then x :: y :: ys else y :: insert x ys
```

This implementation uses a recursive function to sort the list. The `insertion_sort`

function takes a list as input and returns a sorted list. The `insert`

function takes an element `x`

and a sorted list as input and returns a new sorted list with `x`

inserted in the correct position.

## Step-by-step Explanation

- The
`insertion_sort`

function is called with a list as input. - If the list is empty, an empty list is returned.
- Otherwise, the first element
`x`

is removed from the list and the`insert`

function is called with`x`

and the sorted list returned by a recursive call to`insertion_sort`

. - The
`insert`

function takes`x`

and a sorted list as input. - If the list is empty, a list with
`x`

as the only element is returned. - Otherwise, the first element
`y`

is removed from the list and the`insert`

function is called recursively with`x`

and the remaining list`ys`

. - If
`x`

is less than`y`

, a new list with`x`

and`y`

followed by`ys`

is returned. - Otherwise, a new list with
`y`

followed by the result of calling`insert`

with`x`

and`ys`

is returned. - The sorted list returned by
`insert`

is returned by`insertion_sort`

.

## Complexity Analysis

The time complexity of insertion sort is O(n^2) in the worst case, where n is the number of elements in the list. This is because each element must be compared to every other element in the list, resulting in n^2 comparisons. However, in the best case (when the list is already sorted), the time complexity is O(n) because each element only needs to be compared to the previous element. The space complexity of insertion sort is O(1) because the algorithm sorts the list in place without using any additional memory.