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)
\]