Введение
Алгоритм сортировки "разделяй и властвуй"
В информатике сортировка слиянием (также часто записывается как mergesort) — это эффективный, универсальный алгоритм сортировки, основанный на сравнениях. Большинство реализаций обеспечивают стабильную сортировку, что означает, что относительный порядок равных элементов сохраняется между входными и выходными данными. Сортировка слиянием — это алгоритм "разделяй и властвуй", изобретённый Джоном фон Нейманом в 1945 году. Подробное описание и анализ сортировки слиянием, выполняемой снизу вверх, появились в отчёте Голдстина и фон Неймана ещё в 1948 году.
Сортировка по объединению в пинг-понг
Вместо слияния двух блоков за раз, слияние "пинг-понг" объединяет четыре блока одновременно. Четыре отсортированных блока одновременно сливаются во вспомогательное пространство в два отсортированных блока, а затем эти два отсортированных блока возвращаются в основную память. Это позволяет избежать операции копирования и сократить общее количество перемещений вдвое. Ранняя реализация в общественном достоянии, объединяющая четыре блока сразу, была реализована в WikiSort в 2014 году. Позже в том же году метод был описан как оптимизация для сортировки терпением и получил название "слияние пинг-понг". Quadsort реализовал этот метод в 2020 году и назвал его "квадрослиянием".
Сортировка по слиянию на месте
Одним из недостатков сортировки слиянием при реализации на массивах является её требование к рабочей памяти O(n). Было предложено несколько методов для уменьшения объема используемой памяти или реализации сортировки слиянием полностью на месте: предложена альтернативная версия сортировки слиянием, использующая постоянный объем дополнительной памяти. Katajainen и др. представили алгоритм, требующий постоянного количества рабочей памяти: достаточно места для хранения одного элемента входного массива и дополнительного места для хранения O(1) указателей в этот массив. Они достигают временной сложности O(n log n) с небольшими константами, но их алгоритм не является стабильным. Было предпринято несколько попыток создания алгоритма слияния на месте, который можно комбинировать со стандартной сортировкой слиянием (сверху вниз или снизу вверх) для получения сортировки слиянием на месте. В этом случае понятие "на месте" можно ослабить, подразумевая "использование логарифмического объема памяти для стека", поскольку стандартная сортировка слиянием требует такого объема памяти для своего стека. Geffert и др. показали, что стабильное слияние на месте возможно за время O(n log n) с использованием постоянного объема вспомогательной памяти, однако их алгоритм сложен и имеет высокие постоянные коэффициенты: слияние массивов длиной n и m может потребовать 5n + 12m + o(m) операций. Этот высокий коэффициент и сложный алгоритм были упрощены и стали более понятными. Bing Chao Huang и Michael A. Langston представили простой линейный по времени алгоритм практичного слияния отсортированного списка с использованием фиксированного объема дополнительной памяти. Они оба опирались на работы Kronrod и других. Алгоритм выполняет слияние за линейное время и использует постоянный объем дополнительной памяти. Он требует лишь немного больше времени в среднем, чем стандартные алгоритмы сортировки слиянием, которым доступно O(n) временных ячеек памяти, менее чем в два раза. Хотя алгоритм значительно быстрее на практике, он также нестабилен для некоторых списков. Однако, используя схожие концепции, им удалось решить эту проблему. Другие алгоритмы слияния на месте включают SymMerge, который имеет общую временную сложность O((n + m) log (n + m)) и является стабильным. Включение такого алгоритма в сортировку слиянием увеличивает её сложность до нелинейной, но всё ещё квазилинейной, O(n (log n)^2). Многие приложения внешней сортировки используют форму сортировки слиянием, при которой входные данные разбиваются на большее количество подсписков, в идеале на такое количество, при котором их слияние позволяет обрабатываемому набору страниц поместиться в основную память. Современный стабильный линейный вариант слияния на месте — это блочная сортировка слиянием, которая создает раздел уникальных значений для использования в качестве области обмена. Объем используемой памяти можно уменьшить до sqrt(n) с помощью бинарного поиска и вращений. Этот метод используется в библиотеке STL C++ и алгоритме quadsort. При некоторой дополнительной нагрузке, описанный выше алгоритм можно модифицировать для использования трех лент. Временная сложность O(n log n) также может быть достигнута с использованием двух очередей, стека и очереди или трех стеков. В противоположном направлении, используя k > двух лент (и O(k) элементов в памяти), можно уменьшить количество операций с лентами в O(log k) раз, используя k/2-путное слияние. Более сложная сортировка слиянием, оптимизирующая использование лент (и дисков), — это полифазная сортировка слиянием.
suggested an alternative version of merge sort that uses constant additional space. Katajainen et al. present an algorithm that requires a constant amount of working memory: enough storage space to hold one element of the input array, and additional space to hold O(1) pointers into the input array. They achieve an O(n log n) time bound with small constants, but their algorithm is not stable. Several attempts have been made at producing an in place merge algorithm that can be combined with a standard (top down or bottom up) merge sort to produce an in place merge sort. In this case, the notion of "in place" can be relaxed to mean "taking logarithmic stack space", because standard merge sort requires that amount of space for its own stack usage. It was shown by Geffert et al. that in place, stable merging is possible in O(n log n) time using a constant amount of scratch space, but their algorithm is complicated and has high constant factors: merging arrays of length n and m can take 5n + 12m + o(m) moves. This high constant factor and complicated in place algorithm was made simpler and easier to understand. Bing Chao Huang and Michael A. Langston presented a straightforward linear time algorithm practical in place merge to merge a sorted list using fixed amount of additional space. They both have used the work of Kronrod and others. It merges in linear time and constant extra space. The algorithm takes little more average time than standard merge sort algorithms, free to exploit O(n) temporary extra memory cells, by less than a factor of two. Though the algorithm is much faster in a practical way but it is unstable also for some lists. But using similar concepts, they have been able to solve this problem. Other in place algorithms include SymMerge, which takes O((n + m) log (n + m)) time in total and is stable. Plugging such an algorithm into merge sort increases its complexity to the non linearithmic, but still quasilinear, O(n (log n)^(2)). Many applications of external sorting use a form of merge sorting where the input get split up to a higher number of sublists, ideally to a number for which merging them still makes the currently processed set of pages fit into main memory. A modern stable linear and in place merge variant is block merge sort which creates a section of unique values to use as swap space. The space overhead can be reduced to sqrt(n) by using binary searches and rotations. This method is employed by the C++ STL library and quadsort. With some overhead, the above algorithm can be modified to use three tapes. O(n log n) running time can also be achieved using two queues, or a stack and a queue, or three stacks. In the other direction, using k > two tapes (and O(k) items in memory), we can reduce the number of tape operations in O(log k) times by using a k/2 way merge. A more sophisticated merge sort that optimizes tape (and disk) drive usage is the polyphase merge sort.
Оптимизация сортировки объединения
На современных компьютерах локальность обращения к памяти может иметь первостепенное значение при оптимизации программного обеспечения, поскольку используются многоуровневые иерархии памяти. Были предложены версии алгоритма сортировки слиянием, учитывающие особенности кэша, операции в которых специально подобраны для минимизации перемещения страниц в и из кэша памяти машины. Например, алгоритм сортировки слиянием с использованием разбиения на блоки прекращает разделение подмассивов, когда достигаются подмассивы размера S, где S – это количество элементов данных, помещающихся в кэш процессора. Каждый из этих подмассивов сортируется на месте с помощью алгоритма сортировки, например, сортировки вставками, чтобы уменьшить количество обращений к памяти, а затем стандартная сортировка слиянием завершается обычным рекурсивным способом. Этот алгоритм показал лучшую производительность на машинах, для которых важна оптимизация кэша.
Параллельная сортировка
Слияние сортировки хорошо распараллеливается благодаря использованию метода "разделяй и властвуй". За годы существования алгоритма было разработано несколько различных параллельных вариантов. Некоторые параллельные алгоритмы сортировки слиянием тесно связаны с последовательным алгоритмом слияния сверху вниз, в то время как другие имеют иную общую структуру и используют метод K-путевого слияния.
Сортировка слияния с параллельным слиянием
Лучший параллелизм можно достичь, используя параллельный алгоритм слияния. Кормен и др. представляют двоичный вариант, который объединяет две отсортированные подпоследовательности в одну отсортированную выходную последовательность.
Параллельная многосторонняя сортировка
Кажется произвольным ограничивать алгоритмы сортировки слиянием бинарным методом слияния, учитывая, что обычно доступно p > 2 процессоров. Более эффективным подходом может быть использование K-путевого слияния, которое является обобщением двоичного слияния и предполагает слияние K отсортированных последовательностей. Этот вариант слияния хорошо подходит для описания алгоритма сортировки на PRAM.
Основная идея
При наличии несортированной последовательности элементов, целью является сортировка этой последовательности с использованием доступных процессоров. Эти элементы распределяются равномерно между всеми процессорами и сортируются локально с помощью последовательного алгоритма сортировки. Следовательно, последовательность состоит из отсортированных последовательностей длины *k*. Для упрощения предположим, что *n* кратно *p*, так что *n* = *p* *k*. Эти последовательности будут использоваться для выполнения выбора из нескольких последовательностей / выбора разделителей. Для *p*, алгоритм определяет элементы-разделители с глобальным рангом. Затем соответствующие позиции этих элементов в каждой последовательности определяются с помощью бинарного поиска, и, таким образом, последовательность далее разбивается на *p* подпоследовательностей длиной *k*. Кроме того, элементы присваиваются процессору *i*, что означает все элементы с рангом от *i-1* *k* до *i* *k* – 1, которые распределены по всем *p* процессорам. Таким образом, каждый процессор получает последовательность отсортированных последовательностей. Тот факт, что ранг элементов-разделителей был выбран глобально, обеспечивает два важных свойства: во-первых, элементы-разделители были выбраны таким образом, чтобы каждый процессор мог по-прежнему обрабатывать *k* элементов после распределения. Алгоритм идеально сбалансирован по нагрузке. Во-вторых, все элементы на процессоре *i* меньше или равны всем элементам на процессоре *i+1*. Следовательно, каждый процессор выполняет p-путное слияние локально и таким образом получает отсортированную последовательность из своих подпоследовательностей. Благодаря второму свойству, дальнейшее p-путное слияние не требуется, результаты нужно только собрать в порядке номеров процессоров.
These sequences will be used to perform a multisequence selection/splitter selection. For , the algorithm determines splitter elements with global rank Then the corresponding positions of in each sequence are determined with binary search and thus the are further partitioned into subsequences with
Furthermore, the elements of are assigned to processor , means all elements between rank and rank , which are distributed over all Thus, each processor receives a sequence of sorted sequences. The fact that the rank of the splitter elements was chosen globally, provides two important properties: On the one hand, was chosen so that each processor can still operate on elements after assignment. The algorithm is perfectly load balanced. On the other hand, all elements on processor are less than or equal to all elements on processor Hence, each processor performs the p way merge locally and thus obtains a sorted sequence from its sub sequences. Because of the second property, no further p way merge has to be performed, the results only have to be put together in the order of the processor number.
Анализ
Во-первых, каждый процессор локально сортирует назначенные ему элементы, используя алгоритм сортировки со сложностью . Затем элементы-разделители должны быть вычислены за время . Наконец, каждая группа разделителей должна быть объединена параллельно каждым процессором за время , используя последовательный p-путевой алгоритм слияния. Таким образом, общее время выполнения определяется как .
.
Практическая адаптация и применение
Многосторонний алгоритм сортировки слиянием обладает высокой масштабируемостью благодаря широким возможностям параллелизации, позволяющим использовать множество процессоров. Это делает алгоритм подходящим кандидатом для сортировки больших объемов данных, таких как те, что обрабатываются в компьютерных кластерах. Кроме того, поскольку в таких системах память обычно не является ограничивающим ресурсом, недостаток пространственной сложности сортировки слиянием становится незначительным. Однако в таких системах становятся важными и другие факторы, которые не учитываются при моделировании на PRAM. Здесь необходимо учитывать следующие аспекты: иерархию памяти, когда данные не помещаются в кэш процессоров, или накладные расходы на связь при обмене данными между процессорами, что может стать узким местом, когда данные больше не могут быть доступны через общую память. Сандерс и др. в своей статье представили алгоритм массово-синхронной параллельной сортировки слиянием на многоуровневых многосторонних системах, который разделяет процессоры на группы размером. Все процессоры сначала выполняют локальную сортировку. В отличие от одноуровневой многосторонней сортировки, эти последовательности затем разделяются на части и назначаются соответствующим группам процессоров. Эти шаги рекурсивно повторяются в этих группах. Это снижает объем коммуникаций и, в частности, позволяет избежать проблем, связанных с большим количеством небольших сообщений. Иерархическая структура базовой реальной сети может быть использована для определения групп процессоров (например, стойки, кластеры). Другие сложные алгоритмы параллельной сортировки могут достигать тех же или лучших временных ограничений с меньшей константой. Например, в 1991 году Дэвид Пауэрс описал параллелизованный алгоритм быстрой сортировки (и связанную с ним поразрядную сортировку), который может работать за время O(log n) на CRCW параллельной машине с произвольным доступом (PRAM) с n процессорами, выполняя разделение неявно. Пауэрс также показал, что конвейерная версия сортировки слиянием Бэтчера за время O((log n)²) в сети сортировки «бабочка» на практике оказывается быстрее, чем его сортировки за O(log n) на PRAM, и он предоставляет подробное обсуждение скрытых накладных расходов при сравнении, поразрядной сортировки и параллельной сортировки.
Сравнение с другими алгоритмами сортировки
Хотя сортировка кучей (heapsort) имеет те же временные границы, что и сортировка слиянием (merge sort), ей требуется только Θ(1) дополнительной памяти, в отличие от Θ(n) у сортировки слиянием. На типичных современных архитектурах эффективные реализации быстрой сортировки (quicksort) обычно превосходят сортировку слиянием при сортировке массивов, хранящихся в оперативной памяти. Быстрая сортировка предпочтительнее, когда размер сортируемых данных невелик, поскольку её пространственная сложность составляет O(log n), что позволяет лучше использовать кэш-память по сравнению с сортировкой слиянием (с пространственной сложностью O(n)). В Java методы `Arrays.sort()` используют сортировку слиянием или оптимизированную быструю сортировку в зависимости от типов данных, а для повышения эффективности реализации переключаются на сортировку вставками при сортировке менее семи элементов массива. Ядро Linux использует сортировку слиянием для своих связных списков. Timsort, оптимизированный гибрид сортировки слиянием и сортировки вставками, используется в различных программных платформах и языках программирования, включая Java и Android, и ранее использовался в Python с версии 2.3 по версию 3.10.