Python

O(n²):

def insertion_sort(array):
    for rightside in range(len(array) - 1):
        rightside += 1

        while rightside > 0:
            leftside = rightside - 1
            if array[leftside] > array[rightside]:
                # Switch sides
                array[rightside], array[leftside] = (
                    array[leftside],
                    array[rightside],
                )
                rightside -= 1
            else: 
		   # Both sides stay as-is
                break

    return array

assert insertion_sort([1, 2, 3]) == [1, 2, 3], True
assert insertion_sort([3, 2, 1]) == [1, 2, 3], True
assert insertion_sort([2, 3, 1]) == [1, 2, 3], True
assert insertion_sort([1, 2, 3, 4]) == [1, 2, 3, 4], True
assert insertion_sort([4, 3, 2, 1]) == [1, 2, 3, 4], True
assert insertion_sort([1, 3, 2, 4]) == [1, 2, 3, 4], True