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

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

Алгоритм был изобретён Джоном фон Нейманом в 1945 году
'''
=== Математическое описание алгоритма ===
'''
Пусть задано множество элементов: S = {a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>n</sub>} с определенным на нем отношением линейного порядка ≤. Требуется найти такую перестановку π ∈ S<sub>n</sub>, что:∀i,j ∈ {1, 2, ..., n}: i < j ⇒ a<sub>π(i)</sub> ≤ a<sub>π(j)</sub>

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

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

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

Операция слияния: MERGE(L, R) = S, где L и R — отсортированные массивы, S — отсортированный массив, содержащий все элементы L и R.
'''
=== Вычислительное ядро алгоритма ===
'''
Вычислительное ядро алгоритма составляет процедура слияния двух отсортированных массивов, которая выполняется на каждом уровне рекурсии и определяет общую производительность алгоритма.
'''
=== Макроструктура алгоритма ===
'''
'''
=== Схема реализации последовательного алгоритма ===
'''
'''
=== Последовательная сложность алгоритма ===
'''
'''
=== Информационный граф ===
'''
'''
=== Ресурс параллелизма алгоритма ===
'''
'''
=== Входные и выходные данные алгоритма ===
'''
'''
=== Свойства алгоритма ===
'''
#
== Программная реализация алгоритма ==
'''
=== Особенности реализации последовательного алгоритма ===
'''
'''
=== Возможные способы и особенности параллельной реализации алгоритма ===
'''
'''
=== Результаты прогонов ===
'''
'''
=== Выводы для классов архитектур ===
'''
#
== Литература ==
Knuth D.E. The Art of Computer Programming. Volume 3: Sorting and Searching. – 2nd ed. – Addison-Wesley, 1998. – 780 p.