# Insertion Sort

## Idea

**To add a next element to a sorted subarray, move greater elements right and insert that element into the appropriate place.**

For example, we have the subarray from `1`

to `5`

sorted and `3`

to insert.

First, we move `4`

and `5`

right:

And finally, we insert `3`

:

## Time complexity

### Worst case

When inserting each element, the whole subarray is moved (this takes place for arrays sorted in reverse order), which leads to arithmetic progression $1 + 2 + … + (n-1) = O(n^2)$.

### Best case

When inserting each element, nothing is moved, i.e. the input is already sorted. In this case, we just traverse the array once, which requires $O(n)$ operations.

### Average case

It depends on what is considered “average”.

For a length of $n$, let’s consider all permutations of sequence `1`

to `n`

and calculate the average number of moves per sequence.
Note that **the number of moves done by the insertion sort is exactly the number of inversions in the array**.
**The average number of inversions** in a permutation of $n$ elements is $\frac{n(n-1)}{4} = O(n^2)$.

## Proof

Initially I tried to calculate the number of permutations of length $n$ with $k$ inversions.
These numbers are known as *Mahonian numbers* (see M. Bóna, Combinatorics of Permutations, 2004, p. 43ff).
Fortunately, we don't need to calculate them.

Instead, let's see how desired average numbers of inversions change when increasing $n$. Then we get a recurrence relation and solve it.

Creation of a permutation of length $n$ can be considered as inserting $n$ into a permutation of $\{1,...,n-1\}$.

As a result, each of $(n-1)!$ source permutations become $n$ permutations of length $n$. Inversions of a final permutation come from two sources:

- Inversions of the source permutation.
- Inversions added by inserting.

If we denote the total number of inversions in all permutations of length $n$ by $a_n$, the first source gives $na_{n-1}$ inversions. Regarding the second source, each of $(n-1)!$ source permutations gives $0 + 1 + ... + (n-1)$ inversions. So $a_n = na_{n-1} + (n-1)! \sum_{k=1}^{n-1} k$.

Now it's easy to get a recurrence relation for the average number of inversions: $b_n = \frac{a_n}{n!} = \frac{a_{n-1}}{(n-1)!} + (n-1)/2 = b_{n-1} + \frac{n-1}{2}$.

The generating function: $G(z) = \sum_{n=1}^\infty b_n z^n = \sum_{n=2}^\infty (b_{n-1} + \frac{n-1}{2}) z^n = \sum_{n=2}^\infty b_{n-1} z^n + \sum_{n=2}^\infty \frac{n-1}{2} z^n = zG(z) + \sum_{n=2}^\infty \frac{n-1}{2} z^n$, then $G(z) = \frac{\sum_{n=2}^\infty \frac{n-1}{2} z^n}{1-z}$.

Transform $ \frac{1}{1-z} = \sum_{k=0}^\infty z^k $ and group coefficients in the product of the two sums. Then $ G(z) = \sum_{n=2}^\infty (\sum_{k=2}^n \frac{n(n-1)}{4}) z^n $, so $ b_n = \frac{n(n-1)}{4} $.

## Note that the average number of inversions is 2 times less than the maximum one.

In fact, the corresponding distribution is symmetric.

Permutations of length 3:

Of length 4:

## Stability

An element can be moved only past greater elements, so the order of equal elements never changes, and the sort is **stable**.

## Usage

Although this sort is not asymptotically optimal, its simplicity makes it super fast for short arrays.