Insertion Sort

This article is a stub. It might be missing pseudocode, complexity analysis, or a correctness sketch. It might need some other information which is incomplete perhaps.

Insertion sort

Insertion-Sort(A)

1. for i = 2 to A.length
2. key = A[i]
3. j = i - 1
4. while j > 0 and A[j] > key
5. A[j + 1] = A[j]
6. j = j - 1
7. A[j + 1] = key

Insertion sort is an algorithm for Sorting Problem, arranging an un-ordered list to an ordered list. We assume the first element of the un-ordered list to be ordered such that:

• Subarray: $[1, j-1]$ is sorted.
• Key: $[j]$ is the key we concern with.
• Subarray: $[j+1, A.length]$ is concerned.

As the insertion sort operates, it is guaranteed that $[1, j-1]$ is sorted.

Informal Analysis

Loop Invariant

Initialization

It is true prior to the first iteration of loop. As we start with $j$ as $2$, we assumed it as trivial that $A[1]$ is sorted.

Maintenance

During maintenance, each key points to the right side if the condition at Line $4$ is met, and by Line $7$ an empty space is left to be inserted. After Line $7$ is executed, subarray $[1 \cdot \cdot j]$ is sorted, and afterwards we increment $j$ for next iteration.

Termination

It is known that loop terminates when $j > A.length$. At this occurrence $j=A.length+1$ and subarray $A[1 \cdot\cdot j-1]$ is proven to be sorted during maintenance. Plugging $j$, $A[1 \cdot\cdot A.length + \cancel{1} - \cancel{1}]$.