Insertion Sort

Another elementary but interesting sorting algorithm. Its time complexity is O(n²), so every time the size of an array to be sorted is doubled, the efforts quadruple.

Insertion sort starts from index 1 by remembering its value and comparing to the value under index 1 – 1. If the value under previous index is less than the remembered one, then we move the previous value to the current position. So to visualise the process, let’s look at the following example:

array_to_be_sorted = [7, 5, 4, 3, -2, 0]

First we remember array[1] value, tmp = 5. Next we compare if array[1] is less than array[0], if it is we move it, so after first iteration our array looks like that: [5, 7, 4, 3, -2, 0]

We repeat the same steps for all the remaining items in the array. Let's look at how our array would look like after the remaining iterations:
 [4, 5, 7, 3, -2, 0]
 [3, 4, 5, 7, -2, 0]
 [-2, 3, 4, 5, 7, 0]
 [-2, 0, 3, 4, 5, 7] 

The interesting fact about this algorithm is that it sorts arrays only when it is necessary. If the array is already sorted nothing major happens, apart from assigning a value to the tmp variable, and then moving it back where it belongs. As the algorithm recognises part of the array that is already sorted and it stops the execution.

Unfortunately best, worst and average cases have O(n²) time complexity, so you wouldn’t use it for serious tasks, but it is worth being familiar with it for the reasons I just described above.

Pseudo code for the insertion sort algorithm:

for curr_item in array - 1
  move all items greater than the curr_item, one position to the right
  insert the curr_item in its appropriate position

Possible implementation in python:

def insertion_sort(array):
    for index in range(1, len(array)):
        tmp = array[index]
        for reverse_index in range(index, 0, -1):
            previous_index = reverse_index - 1
            if tmp < array[previous_index]:
                array[reverse_index] = array[previous_index]
                stop_index = previous_index
        
        array[stop_index] = tmp

    return array