Участник:Bkmish/Сортировка слиянием (последовательный и параллельный варианты)

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

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

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

Последовательная версия алгоритма сортировки слиянием имеет временную сложность [math]\displaystyle{ \Theta(n \log n) }[/math] в лучшем, среднем и худшем случаях. Это происходит потому, что алгоритм разделяет массив на две половины на каждом уровне рекурсии (что требует [math]\displaystyle{ \log n }[/math] уровней), а затем сливает n элементов на каждом уровне, что дает общую временную сложность [math]\displaystyle{ \Theta(n \log n) }[/math]

Параллельная версия алгоритма сортировки слиянием может быть выполнена с использованием различных подходов и, следовательно, имеет различные временные сложности. Так, например, используя один из алгоритмов распараллеливания, можно достичь сложности [math]\displaystyle{ \Theta \left(\frac{n}{(\log n)^2}\right) }[/math]

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

В общем виде алгоритм сортировки слиянием выглядит следующим образом:

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

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

Вычислительное ядро алгоритма сортировки слиянием - это процесс (который состоит из сравнений элементов и перемещения оставшихся элементов) слияния двух отсортированных подмассивов в один отсортированный массив. Этот процесс занимает большую часть времени работы алгоритма.

Литература

• Левитин А. В. Глава 4. Метод декомпозиции: Сортировка слиянием // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 169—172. — 576 с. — ISBN 978-5-8459-0987-9
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.
• Victor J. Duvanenko "Parallel Merge Sort" Dr. Dobb's Journal & blog
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4. (p. 797-805)