Как сделать сортировку массива методом вставки python?

Сортировка вставками (Insertion Sort) — это алгоритм сортировки, на каждом шаге которого массив постепенно перебирается слева направо. При этом каждый последующий элемент размещается так, чтобы он оказался между ближайшими элементами с минимальным и максимальным значением. Подробнее можно прочитать в Википедии.

визуализация алгоритма сортировки вставками

def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        x = array[i]
        j = i

        while j > 0 and array[j - 1] > x:
            array[j] = array[j - 1]
            j -= 1

        array[j] = x

    return array


insertion_sort([6, 5, 3, 8, 9, 1]) # [1, 3, 5, 6, 8, 9]