Участник: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. На каждом шаге используется вспомогательная память для копирования левой и правой части массива, после чего выполняется операция слияния, работающая за линейное время. Алгоритм является стабильным и полностью детерминированным, а его асимптотическая сложность составляет O(nlogn). Благодаря независимости обработки левого и правого подмассивов данная реализация хорошо подходит для последующей параллелизации.

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

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

Результаты прогонов

Результаты выполнения параллельной сортировки слиянием на различных вычислительных платформах

Массив из 100 млн. элементов

Локальный компьютер (8 потоков OpenMP)

Команда: OMP_NUM_THREADS=8 ./mergesort_omp

Результат: 9.01 сек

СК «Ломоносов-2» (8 потоков OpenMP, очередь test)

Команда: sbatch -p test -n 1 --cpus-per-task=8 job_omp_8.sh

Результат: 11.02 сек

Массив из 1 млрд. элементов

Локальный компьютер (8 потоков OpenMP)

Команда: OMP_NUM_THREADS=8 ./mergesort_omp

Результат: не справился с работой

СК «Ломоносов-2» (8 потоков OpenMP, очередь test)

Команда: sbatch -p test -n 1 --cpus-per-task=8 job_omp_8.sh

Результат: 85.9 сек

Исследование масштабируемости на СК «Ломоносов-2»:

Массив 1 млрд. элементов

1 поток: 213,78 сек

2 потока: 178,246 сек

4 потока: 120,722 сек

8 потоков: 88,04 сек

14 потоков: 73,336 сек

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

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

Литература

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