# Insertion Sort

### Implementation:

for i ← 1 to length(A)
j ← i
while j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j ← j - 1


The idea is dead simple: for every element in the array (i-loop), find the location where it belongs in the array and move it there (j-loop).
In the j-loop, j always points to the next unsorted element; if j is bigger than j-1 the two are swapped, j is decreased, and the process is repeated until the element reaches its place.

In python:

def insertion_sort(s):
for i in range(1,len(s)):
j = i
while j > 0 and s[j] < s[j-1]:
s[j], s[j-1] = s[j-1], s[j]
j -=  1
return s


### Analysis

The outer loop runs exactly n-1 times.

The inner loop runs:

1. In the best case, never: the array is already sorted
2. In the worst case, j-1 times for every iteration of the outer loop (the array is reversed). This is the arithmetic series:
$T(N) = \sum_{j = 2}^{n} (j – 1) = \frac{n(n-1)}{2} = O(N^2)$