insertion_sort.py

def insertion_sort(lst_):
    # Робимо копію вхідного списку lst_, щоб не змінювати оригінал
    lst = lst_[:] 

    # Проходимо по елементах списку, починаючи з другого елемента, i представляє індекс поточного елемента
    for i in range(1, len(lst)):
        # Зберігаємо поточний елемент у змінну key
        key = lst[i]

        # Встановлюємо j на індекс попереднього елемента
        j = i - 1
        # Порівнюємо key з елементами в відсортованій частині списку
        # Поки j не вийшов за межі списку (не менше 0) і значення key менше за значення на позиції j, виконуємо цикл
        while j >= 0 and key < lst[j]:
            
            # Переміщуємо елемент lst[j] вправо, щоб звільнити місце для вставки key
            lst[j + 1] = lst[j]

            # щоб вийти з циклу встановлюємо j на 1 менше чим перший елемент, тобто такого елемента немає
            j -= 1 
        
        # Вставляємо key на своє місце в відсортованій частині списку
        lst[j + 1] = key 
    return lst