Вот еще два варианта, мне подойдет любой, может для вас попроще будет какой?
Вариант 3.
Цикл While процедуры “Сортировка вставками просматривает элементы отсортированного участка А[1…j-1] подряд.
Вместо последовательного просмотра использовать двоичный поиск. Определить Ө для двоичного поиска.Удастся ли таким образом сделать общее время сортировки Ө(n log n)?
Двоичный поиск: сравнить искомый элемент с искомым элементом массива и определить в какой половине массива он находится, а затем применить эту процедуру последовательно к получающимся половинам. Программа может быть реализована циклом или рекурсией.
Сравнить временные характеристики трёх алгоритмов: вставками, вставками с двоичным поиском и рекурсией, с двоичным поиском циклами.
Вариант 6
Оформить сортировку вставками как рекурсивную процедуру: желая сортировать A[1..n], мы (рекурсивно) сортируем A[1..n-1], а затем ставим A[n] на правильное место в отсортированном массиве A[1..n-1].
Написать рекуррентные отношения для времени работы такой процедуры и найти оценку O(g(n))=T(n).
Сравнить эту оценку с начальной сортировкой вставками и слиянием.
