Insertion sort

Algorithm

def insertion(a):
    """
    Implements the insertion sort algorithm
    """

    for i in range(0, len(a) - 1):
        if a[i] < a[i+1]:
            continue

        insert_index = i+1
        insert_element = a[i+1]
        for j in range(i,-1,-1):
            if a[j+1] < a[j]:
                temp = a[j+1]
                a[j+1] = a[j]
                a[j] = temp
    return a

def insertion2(a):
    """
    Implements the insertion sort algorithm.
    """

    if len(a) == 1:
        return a

    for i in range(1, len(a)):
        if a[i] > a[i-1]:
            continue

        for j in range(i,0,-1):
            if a[j] < a[j-1]:
                a[j], a[j-1] = a[j-1], a[j]

    return a

Key concepts

• Insert the current element where it belongs.
• It will be inserted in an already sorted subarray.
• Start looking for a place to insert the element from the current index and move towards the beginning of the array.

Step by step

array = [1,0,3,4,2,5]

i = 0
    a[0] < a[1] | 1 < 0 | False

    insert_index = 1
    insert_element = 0
    j = 0
        a[1] < a[0] | 0 < 1 | True
        temp = a[1] | temp = 0
        a[1] = a[0] | a[1] = 1
        a[0] = temp | a[0] = 0

    array = [0,1,3,4,2,5]

i = 1
    a[1] < a[2] | True

    array = [0,1,3,4,2,5]

i = 2
    a[2] < a[3] | 3 < 4 | True

    array = [0,1,3,4,2,5]

i = 3
    a[3] < a[4] | 4 < 2 | False

    insert_index = 4
    insert_element = 2
    j = 3
        a[4] < a[3] | 2 < 4 | True
        temp = a[4] | temp = 2
        a[4] = a[3] | a[4] = 4
        a[3] = temp | a[3] = 2

    array = [0,1,3,2,4,5]

    j = 2
        a[3] < a[2] | 2 < 3 | True
        temp = a[3] | temp = 2
        a[3] = a[2] | a[3] = 3
        a[2] = temp | a[2] = 2

    array = [0,1,2,3,4,5]

    j = 1
        a[2] < a[1] | 2 < 1 | False

    j = 0
        a[1] < a[0] | 1 < 0 | False

    array = [0,1,2,3,4,5]

i = 4
    a[4] < a[5] | 4 < 5 | True

Complexity analysis

Time

For each element of the array, we compare it with all the previous elements of the array. This gives us 1 in the best case and N in the worst case. This gives us N/2 in the average case. So O(N) = N (N/2) = N²/2.

One could further argue that half of the times (for the average case) the elements we are comparing are already sorted and thus there is no need to do the insertion part of the algorithm with the N²/2 cost. In that case, we can write the computational cost as: O(N) = (1/2)(N²/2) = (N²/4)

Space

We use the same array that is passed as argument and a few more variables, so the cost is: O(N) = N + K ≈ N.

Use cases

This algorithm is specially useful for arrays that are:

• Partially sorted
• Tiny

Examples:

• Array where each entry is not far from its final position
• Arrays in which only a few entries are not sorted
• Arrays that are a concatenation of two sorted arrays