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

- In the best case, never: the array is already sorted
- 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)

\]