2.3.3 Анализ времени работы сортировки слиянием через геометрическую интерпретацию

На каждом из уровней рекурсии количество сортируемых элементов не изменяется. Известно также, что при слиянии отсортированных массивов каждый элемент проходит через «соревнование» курсоров, копируясь в целевой массив. Это означает, что суммарные затраты на перемещение элементов разными ветками рекурсии по срезу одной глубины будут равны. Если отбросить связи между элементами в рассматриваемом дереве рекурсии, то оно может быть вписано в прямоугольник с основанием шириной n (размер входа, т.е. количество элементов исходного массива), где n – количество элементов на входе алгоритма. Высота же прямоугольника будет равна высоте дерева, т.е. log n. Таким образом, временные затраты на обратный ход рекурсии составят n · log n. Прямой ход рекурсии не требует столь большого количества вычислительных ресурсов (там нет перемещения элементов из массива в массив), но, тем не менее, количество вызовов прямо пропорционально объему массива, а, следовательно, также описывается как n · log n, пусть и с меньшей константой. Аналогичным способом может оцениваться время работы любой сортировки сравнениями, работающей по принципу «разделяй и властвуй».

Рисунок 2.3 – Геометрическая интерпретация алгоритма сортировки слиянием