# # Insertion Sort

``````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:

1. `[5, 2, 4, 6, 1, 3]`
2. `[2, 5, 4, 6, 1, 3]`
3. `[2, 4, 5, 6, 1, 3]`
4. `[2, 4, 5, 6, 1, 3]`
5. `[1, 2, 4, 5, 6, 3]`
6. `[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 En be the total average number of exchange to sort array of N element. E1 = 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 Cn be the total average number of comparison to sort array of N element. C1 = 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) 