Insertion sort is an in-place sorting algorithm which builds the sorted list one item at a time.

Time complexity :

Average case : O(n2)

Best case : O(n)

Worst case : O(n2)

Worst case space complexity : O(n)

How the algorithm works:

  • In each iteration, an item to the right of the sorted list (initially empty) is picked.

  • Starting from the rightmost element, swapping between the current item and preceeding item are made, if the preceeding item is smaller. This process stops if the preceeding item is greater than or equal to the current item.

Implementation in Python :

def insertionsort(list):
    for ix in range(1, len(list)):
        jx = ix
        while jx > 0 and list[jx-1] > list[jx]:
            temp = list[jx]
            list[jx] = list[jx-1]
            list[jx-1] = temp
            jx -= 1
    return list

if __name__ == "__main__":

Output :

[-3, -2, -1, 0, 1, 2, 3, 4, 5, 6]