Параметры функции подсказывают Eclipse с PyDev

Слияние Кронрода было первым опубликованным алгоритмом, который сделал это. Это выглядит примерно так:

Разбить обе части массива на блоки размером k = sqrt (n). Сортируйте блоки, используя их первые элементы в качестве основы для сравнения. Это можно сделать в sqrt (n) ^ 2 = O (n) с помощью сортировки по выбору. Ключевое свойство сортировки выбора здесь состоит в том, что он имеет постоянные перемещения на блок, поэтому только #comparisons является квадратным.

После этой фазы для каждого элемента A[i] в массиве под ним находится не более k-1 элементов, «неправильно отсортированных», то есть элементов в позициях j и i, таких что A[j]>A[i]. Они (возможно) находятся в ближайшем блоке под ним, который идет от другой объединенной части. Обратите внимание, что первый элемент блока (и все остальные блоки ниже него) уже правильно отсортированы относительно A[i] из-за блоков, отсортированных по их первым элементам. Вот почему работает вторая фаза, то есть достигается полностью отсортированный массив:

Теперь объедините первый блок со вторым, затем второй с третьим и т. Д., Используя последние 2 блока в качестве временного пространства для вывода. слияния. Это скремблирует содержимое двух последних блоков, но на последнем этапе они (вместе с предыдущим блоком) могут быть отсортированы по сортировке выбора за время sqrt (n) ^ 2 = O (n).