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

1. Inversions of the source permutation.
2. 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.