Сортировка вставками

Сортировка вставками строит отсортированную часть слева, по очереди беря очередной элемент и вставляя его в нужную позицию сдвигом. Эффективна на малых и почти отсортированных массивах.

Сложность: время O(n^2) в среднем и худшем случае, O(n) на почти отсортированных данных. Память: O(1), устойчивая, на месте.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a