# # Insertion Sort

## # Haskell Implementation

```
insertSort :: Ord a => [a] -> [a]
insertSort [] = []
insertSort (x:xs) = insert x (insertSort xs)
insert :: Ord a => a-> [a] -> [a]
insert n [] = [n]
insert n (x:xs) | n <= x = (n:x:xs)
| otherwise = x:insert n xs
```

## # Algorithm Basics

Insertion sort is a very simple, stable, in-place sorting algorithm. It performs well on small sequences but it is much less efficient on large lists. At every step, the algorithms considers the i-th element of the given sequence, moving it to the left until it is in the correct position.

**Graphical Illustration**

**Pseudocode**

```
for j = 1 to length(A)
n = A[j]
i = j - 1
while j > 0 and A[i] > n
A[i + 1] = A[i]
i = i - 1
A[i + 1] = n
```

**Example**

Consider the following list of integers:

```
[5, 2, 4, 6, 1, 3]
```

The algorithm will perform the following steps:

`[5, 2, 4, 6, 1, 3]`

`[2, 5, 4, 6, 1, 3]`

`[2, 4, 5, 6, 1, 3]`

`[2, 4, 5, 6, 1, 3]`

`[1, 2, 4, 5, 6, 3]`

`[1, 2, 3, 4, 5, 6]`

## # C# Implementation

```
public class InsertionSort
{
public static void SortInsertion(int[] input, int n)
{
for (int i = 0; i < n; i++)
{
int x = input[i];
int j = i - 1;
while (j >= 0 && input[j] > x)
{
input[j + 1] = input[j];
j = j - 1;
}
input[j + 1] = x;
}
}
public static int[] Main(int[] input)
{
SortInsertion(input, input.Length);
return input;
}
}
```

**Auxiliary Space:** `O(1)`

**Time Complexity:** `O(n)`

#### # Remarks

When we analyze the performance of the sorting algorithm, we interest primarily on the number of comparison and exchange.

### # Average Exchange

Let E_{n} be the total average number of exchange to sort array of N element. E_{1} = 0 (we do not need any exchange for array with one element). The average number of exchange to sort N element array is the sum of average number of number of exchange to sort N-1 element array with the average exchange to insert the last element into N-1 element array.

Simplify the summation (arithmetic series)

Expands the term

Simplify the summation again (arithmetic series)

### # Average Comparison

Let C_{n} be the total average number of comparison to sort array of N element. C_{1} = 0 (we do not need any comparison on one element array). The average number of comparison to sort N element array is the sum of average number of number of comparison to sort N-1 element array with the average comparison to insert the last element into N-1 element array. If last element is largest element, we need only one comparison, if the last element is the second smallest element, we need N-1 comparison. However, if last element is the smallest element, we do not need N comparison. We still only need N-1 comparison. That is why we remove 1/N in below equation.

Simplify the summation (arithmetic series)

Expand the term

Simplify the summation again (arithmetic series and harmonic number)