Введение
Алгоритм, объединяющий несколько отсортированных списков в один. Алгоритмы слияния — это семейство алгоритмов, которые принимают на вход несколько отсортированных списков и выдают один отсортированный список, содержащий все элементы входных списков. Эти алгоритмы используются как подпрограммы в различных алгоритмах сортировки, наиболее известным из которых является сортировка слиянием.
Merge algorithms are a family of algorithms that take multiple sorted lists as input and produce a single list as output, containing all the elements of the inputs lists in sorted order. These algorithms are used as subroutines in various sorting algorithms, most famously merge sort.
Применение
Алгоритм слияния играет критически важную роль в алгоритме сортировки слиянием, алгоритме сортировки, основанном на сравнении. Концептуально алгоритм сортировки слиянием состоит из двух шагов:
Рекурсивно делить список на подсписки примерно одинаковой длины, пока каждый подсписок не будет содержать только один элемент, или, в случае итеративной (снизу вверх) сортировки слиянием, рассматривать список из n элементов как n подсписков размера 1. Список, содержащий один элемент, по определению считается отсортированным. Повторно объединять подсписки для создания нового отсортированного подсписка, пока единый список не будет содержать все элементы. Этот единый список и является отсортированным списком. Алгоритм слияния используется многократно в алгоритме сортировки слиянием. Пример сортировки слиянием приведен на иллюстрации. Он начинается с несортированного массива из 7 целых чисел. Массив разделяется на 7 разделов, каждый из которых содержит 1 элемент и уже отсортирован. Затем отсортированные разделы объединяются для получения более крупных отсортированных разделов, пока не останется 1 раздел – отсортированный массив.
Параллельное объединение двух списков
Существуют также алгоритмы, которые вводят параллелизм в рамках одного экземпляра слияния двух отсортированных списков. Они могут использоваться в программируемых логических интегральных схемах (FPGA), специализированных схемах сортировки, а также в современных процессорах с инструкциями SIMD (одна инструкция – множественные данные). Существующие параллельные алгоритмы основаны на модификациях части слияния либо битонической сортировки, либо сортировки нечетно-четными проходами. В 2018 году Saitoh M. и др. представили MMS для FPGA, который был направлен на устранение многоциклового контура обратной связи, препятствовавшего эффективной конвейерной обработке в аппаратном обеспечении. Также в 2018 году Papaphilippou P. и др. представили FLiMS.
Python (англ.)
Стандартная библиотека Python (начиная с версии 2.6) также содержит функцию в модуле `heapq`, которая принимает несколько отсортированных итерируемых объектов и объединяет их в один итератор.