Задачи сортировки

Алгоритм сортировки слиянием
Реализовано на Питоне по книге Шень - программирование. Теоремы и задачи. Сложность алгоритма выражается через O-большое от некоторой функции. Например, если сложность алгоритма - O(n²), значит, что число операций в нем не больше чем C*n², где С - некоторая константа. Сложность же данного алгоритма составляет n*log(n). Для меня еще непонятно, как же выяснить сложность алгоритма. Ну, я понимаю когда сложность выражается степенью n. Сколько вложенных циклов от 1 до n, такова и степень в формуле сложности. Я вижу в формуле только один цикл по n, он как бы состоит из двух вложенных: по t+k и второй по p0, q0. Вместе они по-моему представляют из себя цикл по n. Значит, цикл верхнего уровня вносит в формулу сложности log(n).
http://pastebin.com/1mZ8vuZk
Есть еще реализация алгоритма сортировки пузырьком: http://pastebin.com/E5CvSdzz самая простая, поэтому сложность её O(n²).
Сортировка вставками, или Insert Sort
В основе лежит индекс i. В любой момент времени мы можем сказать, что массив a[1]..a[i] является упорядоченным. Но не более того.
Хорошим показателем сортировки является весьма естественное поведение: почти отсортированный массив будет досортирован очень быстро. Это, вкупе с устойчивостью алгоритма, делает метод хорошим выбором в соответствующих ситуациях. Реализация использует сторожевой элемент, который ставится в начало алгоритма - чтобы исключить одно из условий проверки. Он гарантированно меньше всех элементов. Сложность алгоритма приводится в среднем и в худшем случае: O(n²)
Быстрая сортировка
Метод основан на выборе опорного элемента, который делит массив на две части. После выбора начинаем двигаться с разных концов к опорному элементу, если в левой части встречается элемент который больше опорного элемента, а правая - аналогично, меньше, то меняем их местами. Это называется разделение. Потом рекурсивно запускаем процедуру для обеих частей массива.
Каждое разделение требует n шагов, а глубина рекурсии в среднем равна log(n). Поэтому сложность алгоритма равна n*log(n). Но он неустойчив. Например, выбирая максимальный элемент из каждой части опорным элементом при процедуре разделения, получим O(n²). Но такая ситуация редкая, её вероятность 2/n. Алгоритм естественен, в случае частичной упорядоченности входного массива, показывает более хорошие результаты.