insertion sort

Insertion sorts involve the creation of a sorted list by shifting items to the right based on their size in relation to each item.

This has the same runtime as bubble sort.

How it works

We have to iterate over the list to determine if any of the indexes need to have their data pushed further in the list. We store a "current" variable that will hold our item while iterating the array.

Copy all of the data until we determine an index that is smaller than the current item we are shifting.

Big-o

The insertion sort runs in very poor time, O(n^2). This is due to the best and worst case scenarios both being O(n) for comparisons.

	Best	Worst
passes	O(1)	O(n)
comparisons	O(n)	O(n)
total	O(n)	O(n^2)
	linear	quadratic

Example implementation

This implementation utilizes Python and is parametrized with Pytest.

def insertion_sort(list: List[int]) -> List[int]:

    length = len(list)
    for i in range(length):
        current_item = list[i]
        j = i - 1
        while j >= 0 and list[j] > current_item:
            list[j + 1] = list[j]
            j -= 1
        list[j + 1] = current_item

    return list


@pytest.mark.parametrize(
    "list",
    [
        ([]),
        ([1]),
        ([1, 2]),
        ([2, 1]),
        ([7, 4, 9, 2]),
        ([8, 7, 4, 2, 1]),
    ],
)
def test_insertion_sort(list):
    list = insertion_sort(list)

    length = len(list)
    for i in range(length):
        for j in range(0, length-i-1):
            assert list[j] <= list[j + 1]