Classic CS algorithm, written in Python and annotated

def insertion_sort(arr):
    # BigO = O(2n)

    # 0 Elements: Exception
    if len(arr) == 0:
        raise Exception('No Elements')

    # 1 Element: Early Return
    if len(arr) == 1:
        return arr


    for i in range(len(arr)):

        # the value to be insertion-sorted
        val = arr[i]


        # Loop backwards, shuffling the values forward through the
        # array, starting at the current 'val' location -1
        j = i-1
        while j >= 0 and arr[j] > val:
            arr[j+1] = arr[j]
            j -= 1

        # insert the value into the sorted location
        arr[j+1] = val


    return arr

Tests….

import pytest
import random
from insertion_sort import insertion_sort


def test_func_exists():
    insertion_sort([1])


def test_sort():
    input = [1,5,3,2,4]
    actual = insertion_sort(input)
    expected = [1,2,3,4,5]
    assert actual == expected


def test_all_same():
    input = [3,3,3,3,3,3,3]
    actual = insertion_sort(input)
    expected = [3,3,3,3,3,3,3]
    assert actual == expected


def test_sort_zero():
    with pytest.raises(Exception):
        insertion_sort([])


def test_sort_lots():
    input = []
    for x in range(1000):
        input.append(random.randint(1,1000))

    actual = insertion_sort(input)
    expected = input
    expected.sort()

    assert actual == expected