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

Сортировка вставками(Insertion sort) удобна для сортировки коротких последовательностей. Именно таким способом обычно соритруют карты: держа в левой руке уже упорядоченные карты и взяв правой рукой очередную карту, мы вставляем её в нужное место, сравнивая с имеющимися идя справа на лево.

Вычеслительная сложность: O(n²)

Реализация на языке Python:

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

Для сортировки по убыванию меняем while i > 0 and array[i-1] < key: