In this post I will implement another basic sorting algorithm – Insertion Sort. The idea of the algorithm is as follows:

• starting from the beginning of the list compare value with the elements on the left (if any)
• swap their position if they are not in the right order
• continue until element on the left is smaller than current element
• after each iteration elements on the left from the current element are sorted

We can visualize insertion sort algorithm by sorting following list [5 1 4 2 8]. I’ll use colors to specify current adjacent pair and already sorted elements.

Iteration #1 : [5 1 4 2 8]

Iteration #2 : [5 1 4 2 8] [5 1 4 2 8] → [1 5 4 2 8]

Iteration #3 : [1 5 4 2 8] [1 5 4 2 8] → [1 4 5 2 8] [1 4 5 2 8] → [1 4 5 2 8]

Iteration #4 : [1 4 5 2 8] [1 4 5 2 8] → [1 4 2 5 8] [1 4 2 5 8] → [1 2 4 5 8] [1 2 4 5 8] → [1 2 4 5 8]

Iteration #5 : [1 2 4 5 8] [1 2 4 5 8] → [1 2 4 5 8]

Implementation of the insertion sort is very simple:

Similarly to bubble and selection sorts we have two loops: outer and inner, so the average complexity is similar as well – O(n²). For best-case scenario (already sorted elements) insertion sort has better complexity – O(n).

Complexity: O(n²).