39
правок
Изменения
Нет описания правки
===Шаг №2. Разбиения на подмассивы и их сортировка===
На данном этапе у нас есть входной массив, его размер <tex>n</tex> и вычисленное число <tex>minrun</tex>. Алгоритм работы этого шага: [[Файл:МассивMinrunExample.pngpng |300px|thumb|right]]
# Указатель текущего элемента ставится в начало входного массива.
# Начиная с текущего элемента, идет поиск во входном массиве упорядоченного подмассива <tex>run</tex>. По определению, в <tex>run</tex> однозначно войдет текущий элемент и следующий за ним. Если получившийся подмассив упорядочен по убыванию — элементы переставляются так, чтобы они шли по возрастанию.
<tex>*</tex> Итак, нужно объединить полученные подмассивы для получения результирующего упорядоченного массива. Для достижения эффективности, объединение должно удовлетворять требованиям:
# Объединять подмассивы примерно равного размера
# Сохранить стабильность алгоритма (не делать бессмысленных перестановок). [[Файл:СлияниеMerge2mas.png|400px|right]]
Алгоритм шага №3:
