Участник: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).

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

Ресурс параллелизма алгоритма

Алгоритм сортировки слиянием имеет рекурсивную структуру: исходный массив делится на части, каждая часть сортируется независимо, после чего отсортированные подмассивы последовательно объединяются в единый массив.

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

Входные и выходные данные алгоритма

На вход алгоритму подаётся:

• Одномерный массив чисел длиной N, который требуется отсортировать по возрастанию A=[a₁​,a₂​,a₃​,…,a_N​]
• Количество процессов P, участвующих в вычислении

На выходе алгоритма формируется отсортированный массив длиной N:

A′ = [a'₁​, a'₂​​, a'₃​​, … , a'_N​], a'₁​ ​≤ a'₂​ ​≤ ⋯ ≤ a'_N​​

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

Алгоритм сортировки слиянием относится к классу рекурсивных алгоритмов типа «разделяй и властвуй» (divide and conquer). Параллельная версия основана на независимой обработке подмножеств данных и их последующем слиянии.

Алгоритм реализует параллелизм по данным — каждый процесс сортирует свою часть массива независимо от других.

Программная реализация алгоритма

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

Последовательный алгоритм сортировки слиянием основан на принципе «разделяй и властвуй» и включает рекурсивное разбиение массива на две части до подмассивов размера 1. На каждом шаге используется вспомогательная память для копирования левой и правой части массива, после чего выполняется операция слияния, работающая за линейное время. Алгоритм является стабильным и полностью детерминированным, а его асимптотическая сложность составляет . Благодаря независимости обработки левого и правого подмассивов данная реализация хорошо подходит для последующей параллелизации.

Возможные способы и особенности параллельной реализации алгоритма

Параллельная реализация сортировки слиянием основана на том, что сортировка левой и правой части массива выполняется независимо, что делает алгоритм естественно распараллеливаемым. Основной принцип параллельной версии заключается в создании отдельных задач (threads или процессов), отвечающих за сортировку подмассивов на различных уровнях рекурсивного дерева.

Выводы для классов архитектур

Сортировка слиянием хорошо масштабируется на MIMD- и гибридных архитектурах благодаря независимому выполнению подзадач. На SIMD-архитектурах её эффективность ограничена, а на SISD работает предсказуемо, но без ускорения. На распределённых системах ключевым фактором становится оптимизация объёма межпроцессных обменов.

Литература

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