Участник:Kiryan/Алгоритм сортировки слиянием

Свойства и структура алгоритмов

Общее описание алгоритма

Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Алгоритм был изобретён Джоном фон Нейманом в 1945 году

Математическое описание алгоритма

Пусть задано множество элементов: S = {a₁, a₂, ..., a_n} с определенным на нем отношением линейного порядка ≤. Требуется найти такую перестановку π ∈ S_n, что:∀i,j ∈ {1, 2, ..., n}: i < j ⇒ a_π(i) ≤ a_π(j)

Алгоритм реализует стратегию «разделяй и властвуй», состоящую из трех этапов:

1. Разделение: Исходный массив рекурсивно делится на две примерно равные части до достижения базового случая (массивы длины 1)
2. Упорядочивание: Базовые случаи (массивы длины 1) по определению являются отсортированными
3. Слияние: Отсортированные подмассивы объединяются в один отсортированный массив

Операция разделения: SPLIT(A, p, r) = (A[p..q], A[q+1..r]), где q = ⌊(p + r)/2⌋

Операция слияния: MERGE(L, R) = S, где L и R — отсортированные массивы, S — отсортированный массив, содержащий все элементы L и R.

Вычислительное ядро алгоритма

Вычислительное ядро алгоритма составляет процедура слияния двух отсортированных массивов, которая выполняется на каждом уровне рекурсии и определяет общую производительность алгоритма.

Макроструктура алгоритма

Алгоритм сортировки слиянием реализует стратегию «разделяй и властвуй» (divide and conquer) и состоит из трех макрофаз:

1. Разделения (Divide). Рекурсивная декомпозиция на подмассивы
2. Базовые случаи (Conquer). Обработка тривиальных подзадач
3. Слияние (Combine). Иерархическое объединение результатов

Схема реализации последовательного алгоритма

Пусть задан массив A = [a₁, a₂, ..., a_n], a_i ∈ R, i = 1, ...,n, требующий сортировки по возрастанию.

Основная идея алгоритма

1. Разделение: массив рекурсивно делится пополам до получения подмассивов длины 1, каждый из которых считается отсортированным.
2. Слияние: два отсортированных подмассива и объединяются в один отсортированный массив. На каждой итерации сравниваются первые элементы подмассивов, меньший элемент добавляется в результирующий массив, и указатель смещается. Процесс продолжается, пока все элементы не будут объединены.

Последовательная сложность алгоритма

На каждом шаге массив размером n делится на две части, каждая из которых рекурсивно сортируется, после чего выполняется операция слияния двух отсортированных подмассивов.

Рекуррентное соотношение для оценки времени работы алгоритма имеет вид:

T(n) = 2T(n/2) + O(n), где O(n) — затраты времени на слияние двух половин массива.

Последовательная временная сложность сортировки слиянием: T(n) = O(nlogn).

Информационный граф

Литература

Knuth D.E. The Art of Computer Programming. Volume 3: Sorting and Searching. – 2nd ed. – Addison-Wesley, 1998. – 780 p.