Сортировка слиянием

Алгоритм сортировки «разделяй и властвуй»

В информатике сортировка слиянием (также часто пишется как mergesort и merge-sort ^[2] ) — это эффективный, универсальный и основанный на сравнении алгоритм сортировки . Большинство реализаций производят стабильную сортировку , что означает , что относительный порядок равных элементов одинаков на входе и выходе. Сортировка слиянием — это алгоритм «разделяй и властвуй» , изобретенный Джоном фон Нейманом в 1945 году. ^[3] Подробное описание и анализ сортировки слиянием снизу вверх появились в отчете Голдстайна и фон Неймана еще в 1948 году. ^[4]

Алгоритм

Концептуально сортировка слиянием работает следующим образом:

1. Разделим несортированный список на n подсписков, каждый из которых содержит один элемент (список из одного элемента считается отсортированным).
2. Повторно объединяйте подсписки для создания новых отсортированных подсписков, пока не останется только один подсписок. Это будет отсортированный список.

Реализация сверху вниз

Пример кода на языке C, использующего индексы для алгоритма сортировки слиянием сверху вниз, который рекурсивно разбивает список (в этом примере называемый запусками ) на подсписки, пока размер подсписка не станет 1, а затем объединяет эти подсписки для получения отсортированного списка. Шаг копирования назад избегается с помощью чередования направления слияния на каждом уровне рекурсии (за исключением первоначального одноразового копирования, которого тоже можно избежать).

В качестве простого примера рассмотрим массив с двумя элементами. Элементы копируются в B[], а затем объединяются обратно в A[]. Если элементов четыре, то при достижении дна уровня рекурсии отдельные элементы из A[] объединяются в B[], а затем на следующем более высоком уровне рекурсии эти двухэлементные элементы объединяются в A[]. Этот шаблон продолжается на каждом уровне рекурсии.

// Массив A[] содержит элементы для сортировки; массив B[] — это рабочий массив. void TopDownMergeSort ( A [], B [], n ) { CopyArray ( A , 0 , n , B ); // однократное копирование A[] в B[] TopDownSplitMerge ( A , 0 , n , B ); // сортировка данных из B[] в A[] }             // Разделить A[] на 2 прогона, отсортировать оба прогона в B[], объединить оба прогона из B[] в A[] // iBegin включительно; iEnd не включает (A[iEnd] не входит в набор). void TopDownSplitMerge ( B [], iBegin , iEnd , A []) { if ( iEnd - iBegin <= 1 ) // если размер прогона == 1 return ; // считать его отсортированным // разделить прогон длиной более 1 элемента на две части iMiddle = ( iEnd + iBegin ) / 2 ; // iMiddle = средняя точка // рекурсивно сортировать оба прогона из массива A[] в B[] TopDownSplitMerge ( A , iBegin , iMiddle , B ); // сортировать левый прогон TopDownSplitMerge ( A , iMiddle , iEnd , B ); // сортируем правый прогон // объединяем полученные прогоны из массива B[] в A[] TopDownMerge ( B , iBegin , iMiddle , iEnd , A ); }                                       // Левая исходная половина — A[ iBegin:iMiddle-1]. // Правая исходная половина — A[iMiddle:iEnd-1 ]. // Результат — B[ iBegin:iEnd-1 ]. void TopDownMerge ( B [], iBegin , iMiddle , iEnd , A []) { i = iBegin , j = iMiddle ; // Пока в левой или правой прогонах есть элементы... for ( k = iBegin ; k < iEnd ; k ++ ) { // Если левая прогонка существует и <= существующей правой прогонке. if ( i < iMiddle && ( j >= iEnd || A [ i ] <= A [ j ])) { B [ k ] = A [ i ]; i = i + 1 ; } else { B [ k ] = A [ j ]; j = j + 1 ; } } }                                                         void CopyArray ( A [], iBegin , iEnd , B []) { for ( k = iBegin ; k < iEnd ; k ++ ) B [ k ] = A [ k ]; }               

Сортировка всего массива выполняется с помощью TopDownMergeSort(A, B, length(A)) .

Реализация снизу вверх

Пример кода на языке C, использующего индексы для алгоритма сортировки слиянием снизу вверх, который обрабатывает список как массив из n подсписков (в этом примере называемых сериями ) размером 1 и итеративно объединяет подсписки туда и обратно между двумя буферами:

// массив A[] содержит элементы для сортировки; массив B[] — это рабочий массив void BottomUpMergeSort ( A [], B [], n ) { // Каждый 1-элементный отрезок в A уже «отсортирован». // Последовательно создаем более длинные отсортированные отрезки длиной 2, 4, 8, 16..., пока весь массив не будет отсортирован. for ( width = 1 ; width < n ; width = 2 * width ) { // Массив A заполнен отрезками длиной width. for ( i = 0 ; i < n ; i = i + 2 * width ) { // Объединить два отрезка: A[i:i+width-1] и A[i+width:i+2*width-1] в B[] // или скопировать A[i:n-1] в B[] ( if (i+width >= n) ) BottomUpMerge ( A , i , min ( i + width , n ), min ( i + 2 * width , n ), B ); } // Теперь рабочий массив B заполнен отрезками длины 2*width. // Копируем массив B в массив A для следующей итерации. // Более эффективная реализация поменяла бы роли A и B. CopyArray ( B , A , n ); // Теперь массив A заполнен отрезками длины 2*width. } }                                                    // Левый отрезок — A[iLeft :iRight-1]. // Правый отрезок — A[iRight:iEnd-1]. void BottomUpMerge ( A [], iLeft , iRight , iEnd , B []) { i = iLeft , j = iRight ; // Пока в левом или правом отрезке есть элементы... for ( k = iLeft ; k < iEnd ; k ++ ) { // Если левый отрезок существует и <= существующему правому отрезку. if ( i < iRight && ( j >= iEnd || A [ i ] <= A [ j ])) { B [ k ] = A [ i ]; i = i + 1 ; } else { B [ k ] = A [ j ]; j = j + 1 ; } } }                                                          void CopyArray ( B [], A [], n ) { for ( i = 0 ; i < n ; i ++ ) A [ i ] = B [ i ]; }              

Реализация сверху вниз с использованием списков

Псевдокод для алгоритма сортировки слиянием сверху вниз, который рекурсивно делит входной список на меньшие подсписки до тех пор, пока подсписки не будут тривиально отсортированы, а затем объединяет подсписки, возвращаясь вверх по цепочке вызовов.

function merge_sort( list m) is // Базовый случай. Список из нуля или одного элемента сортируется по определению.  если длина m ≤ 1, то  вернуть m // Рекурсивный случай. Сначала разделим список на подсписки одинакового размера , // состоящие из первой половины и второй половины списка. // Это предполагает, что списки начинаются с индекса 0.  var left := пустой список var right := пустой список для каждого x с индексом i в m do  if i < (длина m)/2 then добавить x слева еще добавить x справа // Рекурсивно сортируем оба подсписка. слева := merge_sort(слева) справа := merge_sort(справа) // Затем объединим отсортированные подсписки. возврат слияния (слева, справа)

В этом примере функция merge объединяет левый и правый подсписки.

функция merge(left, right) — это  var result := пустой список пока левое не пусто и правое не пусто do  if first(left) ≤ first(right) then добавить первый (слева) к результату слева := остаток(слева) еще добавить первый(справа) к результату справа := остальное(справа) // Элементы left могут быть как left, так и right; используйте их. // (Фактически будет выполнен вход только в один из следующих циклов.)  while left is not empty do добавить первый (слева) к результату слева := остаток(слева) пока справа не пусто делать добавить первый(справа) к результату справа := остальное(справа) вернуть результат

Реализация снизу вверх с использованием списков

Псевдокод для алгоритма сортировки слиянием снизу вверх, который использует небольшой массив фиксированного размера ссылок на узлы, где array[i] — это либо ссылка на список размером 2 ^i, либо nil . node — это ссылка или указатель на узел. Функция merge() будет похожа на ту, что показана в примере списков слияния сверху вниз, она объединяет два уже отсортированных списка и обрабатывает пустые списки. В этом случае merge() будет использовать node для своих входных параметров и возвращаемого значения.

функция merge_sort( голова узла ) — это // вернуть, если список пустой если head = nil , то  вернуть nil var  node array[32]; изначально все nil var  node result var  node next var  int i результат := голова // объединить узлы в массив пока результат ≠ ноль сделать следующий := результат.следующий; результат.следующий := ноль для (i = 0; (i < 32) && (array[i] ≠ nil); i += 1) сделать результат := merge(массив[i], результат) массив[i] := ноль // не выходить за конец массива если я = 32 , то я -= 1 массив[i] := результат результат := следующий // объединить массив в один список результат := ноль для (i = 0; i < 32; i += 1) сделать результат := merge(массив[i], результат) вернуть результат

Реализация сверху вниз в декларативном стиле

Псевдокод, подобный Haskell , показывающий, как сортировка слиянием может быть реализована на таком языке с использованием конструкций и идей функционального программирования .

merge_sort :: [ a ] ​​-> [ a ] ​​merge_sort ( [ ] ) = [] merge_sort ( [ x ] ) = [ x ] merge_sort ( xs ) = merge ( merge_sort ( left ), merge_sort ( right )) где ( left , right ) = split ( xs , length ( xs ) / 2 ) merge :: ( [ a ], [ a ]) -> [ a ] ​​merge ( [ ] , xs ) = xs merge ( xs , [ ] ) = xs merge ( x : xs , y : ys ) | if x ≤ y = x : merge ( xs , y : ys ) | else = y : merge ( x : xs , ys )                                                          

Анализ

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

При сортировке n объектов сортировка слиянием имеет среднюю и худшую производительность O ( n  log  n ) сравнений. Если время выполнения (количество сравнений) сортировки слиянием для списка длины n равно T ( n ), то рекуррентное соотношение T ( n ) = 2 T ( n /2) + n следует из определения алгоритма (применяем алгоритм к двум спискам размером в два раза меньше исходного списка и добавляем n шагов, предпринятых для слияния двух полученных списков). ^[5] Закрытая форма следует из основной теоремы для рекуррентных уравнений «разделяй и властвуй» .

Число сравнений, выполняемых сортировкой слиянием в худшем случае, задается числами сортировки . Эти числа равны или немного меньше ( n  ⌈ lg  n ⌉ − 2 ^{⌈lg  n ⌉} + 1), что находится между ( n  lg  n − n + 1) и ( n  lg  n + n + O(lg  n )). ^[6] Лучший случай сортировки слиянием занимает примерно половину итераций, чем худший случай. ^[7]

Для больших n и случайно упорядоченного входного списка ожидаемое (среднее) число сравнений сортировки слиянием приближается к α · n меньше, чем в худшем случае, где ${\displaystyle \alpha =-1+\sum _{k=0}^{\infty }{\frac {1}{2^{k}+1}}\approx 0.2645.}$

В худшем случае сортировка слиянием использует примерно на 39% меньше сравнений, чем быстрая сортировка в среднем случае, а с точки зрения ходов сложность сортировки слиянием в худшем случае составляет O ( n  log  n ) — такая же сложность, как и в лучшем случае быстрой сортировки. ^[7]

Сортировка слиянием более эффективна, чем быстрая сортировка для некоторых типов списков, если к сортируемым данным можно эффективно обращаться только последовательно, и поэтому она популярна в таких языках, как Lisp , где структуры данных с последовательным доступом очень распространены. В отличие от некоторых (эффективных) реализаций быстрой сортировки, сортировка слиянием является стабильной сортировкой.

Наиболее распространенная реализация сортировки слиянием не сортирует на месте; ^[8] поэтому для сохранения отсортированных выходных данных необходимо выделить объем памяти, соответствующий размеру входных данных (см. ниже варианты, для которых требуется только n /2 дополнительных пробелов).

Естественная сортировка слиянием

Естественная сортировка слиянием похожа на сортировку слиянием снизу вверх, за исключением того, что эксплуатируются любые естественно возникающие прогоны (отсортированные последовательности) во входных данных. Могут эксплуатироваться как монотонные, так и битонные (чередующиеся вверх/вниз) прогоны, при этом списки (или эквивалентные ленты или файлы) являются удобными структурами данных (используемыми как очереди FIFO или стеки LIFO ). ^[9] В сортировке слиянием снизу вверх отправная точка предполагает, что каждый прогон имеет длину в один элемент. На практике случайные входные данные будут иметь много коротких прогонов, которые просто случайно отсортированы. В типичном случае естественной сортировке слиянием может не потребоваться столько проходов, потому что для слияния требуется меньше прогонов. В лучшем случае входные данные уже отсортированы (т. е. представляют собой один прогон), поэтому естественной сортировке слиянием нужно сделать только один проход по данным. Во многих практических случаях присутствуют длинные естественные прогоны, и по этой причине естественная сортировка слиянием используется как ключевой компонент Timsort . Пример:

Начало: 3 4 2 1 7 5 8 9 0 6Выберите пробежки: (3 4)(2)(1 7)(5 8 9)(0 6)Объединить: (2 3 4)(1 5 7 8 9)(0 6)Объединить: (1 2 3 4 5 7 8 9)(0 6)Объединить: (0 1 2 3 4 5 6 7 8 9)

Формально естественная сортировка слиянием называется оптимальной по количеству запусков, где — количество запусков в минус один. ${\displaystyle {\mathtt {Runs}}(L)}$ ${\displaystyle L}$

Турнирные сортировки с заменой и выбором используются для сбора начальных запусков для внешних алгоритмов сортировки.

Сортировка методом пинг-понга слиянием

Вместо объединения двух блоков за раз, пинг-понговое слияние объединяет четыре блока за раз. Четыре отсортированных блока одновременно объединяются во вспомогательном пространстве в два отсортированных блока, затем два отсортированных блока объединяются обратно в основную память. Это позволяет исключить операцию копирования и сократить общее количество ходов вдвое. Ранняя реализация общедоступного слияния четырех блоков была разработана WikiSort в 2014 году, позже в том же году метод был описан как оптимизация для сортировки с терпением и назван пинг-понговым слиянием. ^{[10] [11]} Quadsort реализовал метод в 2020 году и назвал его quad merge. ^[12]

Сортировка слиянием на месте

Одним из недостатков сортировки слиянием, реализованной на массивах, является ее потребность в рабочей памяти O ( n ) . Было предложено несколько методов уменьшения памяти или полной реализации сортировки слиянием на месте :

• Кронрод (1969) предложил альтернативную версию сортировки слиянием, которая использует постоянное дополнительное пространство.
• Катаяйнен и др. представляют алгоритм, требующий постоянного объема рабочей памяти: достаточно места для хранения одного элемента входного массива и дополнительное место для хранения O (1) указателей на входной массив. Они достигают временного ограничения O ( n log n ) с небольшими константами, но их алгоритм нестабилен. ^[13]
• Было предпринято несколько попыток создания алгоритма слияния на месте , который можно объединить со стандартной (сверху вниз или снизу вверх) сортировкой слиянием для создания сортировки слиянием на месте. В этом случае понятие «на месте» можно ослабить, чтобы оно означало «занятие логарифмического пространства стека», поскольку стандартная сортировка слиянием требует такого количества пространства для собственного использования стека. Было показано Геффертом и др. , что стабильное слияние на месте возможно за время O ( n log n ) с использованием постоянного количества рабочего пространства, но их алгоритм сложен и имеет высокие постоянные факторы: слияние массивов длины n и m может занять 5 n + 12 m + o ( m ) ходов. ^[14] Этот высокий постоянный фактор и сложный алгоритм на месте были упрощены и понятны. Бинг-Чао Хуан и Майкл А. Лэнгстон ^[15] представили простой алгоритм линейного времени практического слияния на месте для слияния отсортированного списка с использованием фиксированного количества дополнительного пространства. Они оба использовали работу Кронрода и других. Он объединяется за линейное время и постоянное дополнительное пространство. Алгоритм занимает немного больше времени в среднем, чем стандартные алгоритмы сортировки слиянием, свободно используя O(n) временных дополнительных ячеек памяти, менее чем в два раза. Хотя алгоритм намного быстрее на практике, он также нестабилен для некоторых списков. Но используя похожие концепции, они смогли решить эту проблему. Другие алгоритмы на месте включают SymMerge, который занимает O (( n + m ) log ( n + m )) времени в целом и является стабильным. ^[16] Включение такого алгоритма в сортировку слиянием увеличивает его сложность до нелинейной , но все еще квазилинейной , O ( n (log n ) ² ) .
• Во многих приложениях внешней сортировки используется форма сортировки слиянием, при которой входные данные разделяются на большее количество подсписков, в идеале — на такое количество, при котором их объединение по-прежнему позволяет уместить текущий обрабатываемый набор страниц в основную память.
• Современный стабильный вариант линейной сортировки слиянием на месте — это сортировка слиянием блоков , которая создает раздел уникальных значений для использования в качестве пространства подкачки.
• Расходы на пространство можно сократить до sqrt( n ) с помощью двоичного поиска и вращения. ^[17] Этот метод используется библиотекой C++ STL и quadsort. ^[12]
• Альтернативой для сокращения копирования в несколько списков является связывание нового поля информации с каждым ключом (элементы в m называются ключами). Это поле будет использоваться для связывания ключей и любой связанной с ними информации в отсортированном списке (ключ и связанная с ним информация называются записью). Затем происходит слияние отсортированных списков путем изменения значений ссылок; никакие записи не нужно перемещать вообще. Поле, содержащее только ссылку, обычно будет меньше всей записи, поэтому также будет использоваться меньше места. Это стандартный метод сортировки, не ограниченный сортировкой слиянием.
• Простой способ сократить накладные расходы пространства до n /2 — сохранить left и right как объединенную структуру, скопировать только левую часть m во временное пространство и указать процедуре слияния поместить объединенный вывод в m . В этой версии лучше выделить временное пространство вне процедуры слияния , так что потребуется только одно выделение. Излишнее копирование, упомянутое ранее, также смягчается, поскольку последняя пара строк перед оператором return result (функция merge в псевдокоде выше) становится лишней.

Использование с ленточными накопителями

Алгоритмы типа сортировки слиянием позволяли сортировать большие наборы данных на ранних компьютерах, которые имели небольшую по современным стандартам память с произвольным доступом. Записи хранились на магнитной ленте и обрабатывались на банках магнитных ленточных накопителей, таких как эти IBM 729 .

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

Называя четыре ленточных накопителя как A, B, C, D, с исходными данными на A, и используя только два буфера записи, алгоритм похож на реализацию снизу вверх, используя пары ленточных накопителей вместо массивов в памяти. Основной алгоритм можно описать следующим образом:

1. Объединить пары записей из A; записать подсписки из двух записей поочередно в C и D.
2. Объединить двухзаписные подсписки из C и D в четырехзаписные подсписки, записывая их поочередно в A и B.
3. Объединить подсписки из четырех записей из A и B в подсписки из восьми записей; записать их поочередно в C и D
4. Повторяйте до тех пор, пока не получите один список, содержащий все данные, отсортированные за log ₂ ( n ) проходов.

Вместо того, чтобы начинать с очень коротких запусков, обычно используется гибридный алгоритм , где начальный проход считывает много записей в память, выполняет внутреннюю сортировку для создания длинного запуска, а затем распределяет эти длинные запуски в выходной набор. Этот шаг позволяет избежать многих ранних проходов. Например, внутренняя сортировка 1024 записей сэкономит девять проходов. Внутренняя сортировка часто бывает большой, потому что она имеет такое преимущество. Фактически, существуют методы, которые могут сделать начальные запуски длиннее доступной внутренней памяти. Один из них, «снегоочиститель» Кнута (основанный на двоичной минимальной куче ), генерирует запуски вдвое длиннее (в среднем), чем размер используемой памяти. ^[18]

С некоторыми накладными расходами приведенный выше алгоритм можно модифицировать для использования трех лент. Время выполнения O ( n log n ) также может быть достигнуто с использованием двух очередей , или стека и очереди, или трех стеков. В другом направлении, используя k > двух лент (и O ( k ) элементов в памяти), мы можем сократить количество операций с лентами в O (log k ) раз, используя k/2-way merge .

Более сложная сортировка слиянием, оптимизирующая использование ленточного (и дискового) накопителя, — это полифазная сортировка слиянием .

Оптимизация сортировки слиянием

Сортировка слиянием плиток, примененная к массиву случайных целых чисел. Горизонтальная ось — индекс массива, а вертикальная ось — целое число.

На современных компьютерах локальность ссылок может иметь первостепенное значение в оптимизации программного обеспечения , поскольку используются многоуровневые иерархии памяти . Были предложены версии алгоритма сортировки слиянием, поддерживающие кэш , операции которого были специально выбраны для минимизации перемещения страниц в кэш памяти машины и из него. Например,Алгоритм сортировки слиянием плитки прекращает разбиение подмассивов, когда достигаются подмассивы размера S, где S — количество элементов данных, помещающихся в кэш ЦП. Каждый из этих подмассивов сортируется с помощью алгоритма сортировки на месте, такого каксортировка вставкой, чтобы предотвратить подкачки памяти, а затем обычная сортировка слиянием завершается стандартным рекурсивным способом. Этот алгоритм продемонстрировал лучшую производительность^{[ необходим пример ]}на машинах, которые выигрывают от оптимизации кэша. (LaMarca & Ladner 1997)

Параллельная сортировка слиянием

Сортировка слиянием хорошо распараллеливается благодаря использованию метода «разделяй и властвуй» . За эти годы было разработано несколько различных параллельных вариантов алгоритма. Некоторые параллельные алгоритмы сортировки слиянием тесно связаны с последовательным алгоритмом слияния сверху вниз, в то время как другие имеют другую общую структуру и используют метод слияния K-way .

Сортировка слиянием с параллельной рекурсией

Последовательную процедуру сортировки слиянием можно описать в две фазы: фазу деления и фазу слияния. Первая состоит из множества рекурсивных вызовов, которые многократно выполняют один и тот же процесс деления до тех пор, пока подпоследовательности не будут тривиально отсортированы (содержат один или ни одного элемента). Интуитивный подход заключается в распараллеливании этих рекурсивных вызовов. ^[19] Следующий псевдокод описывает сортировку слиянием с параллельной рекурсией с использованием ключевых слов fork и join :

// Сортируем элементы от lo до hi (исключая) массива A. Алгоритм mergesort(A, lo, hi) —  если lo+1 < hi, то // Два или более элементов. середина := ⌊(низ + хай) / 2⌋ fork mergesort(A, lo, mid) сортировка слиянием(A, середина, привет) присоединиться слияние(A, lo, mid, hi)

Этот алгоритм является тривиальной модификацией последовательной версии и плохо распараллеливается. Поэтому его ускорение не очень впечатляет. Он имеет диапазон , что является всего лишь улучшением на по сравнению с последовательной версией (см. Введение в алгоритмы ). Это в основном из-за метода последовательного слияния, поскольку он является узким местом параллельного выполнения. ${\displaystyle \Theta (n)}$ ${\displaystyle \Theta (\log n)}$

Сортировка слиянием с параллельным слиянием

Лучшего параллелизма можно достичь, используя алгоритм параллельного слияния . Кормен и др. представляют бинарный вариант, который объединяет две отсортированные подпоследовательности в одну отсортированную выходную последовательность. ^[19]

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

Следующий псевдокод демонстрирует модифицированный метод сортировки параллельным слиянием с использованием алгоритма параллельного слияния (взятого из работы Кормена и др.).

/** * A: Входной массив * B: Выходной массив * lo: нижняя граница * hi: верхняя граница * выкл.: смещение */алгоритм parallelMergesort(A, lo, hi, B, off) — это len := hi - lo + 1 если len == 1 тогда B[выкл] := A[ло] иначе пусть T[1..len] будет новым массивом середина := ⌊(низ + хай) / 2⌋ середина := середина - ло + 1 fork parallelMergesort(A, lo, mid, T, 1) parallelMergesort(A, середина + 1, привет, T, середина' + 1) присоединиться  parallelMerge(T, 1, mid', mid' + 1, len, B, off)

Чтобы проанализировать рекуррентное отношение для наихудшего случая, рекурсивные вызовы parallelMergesort должны быть включены только один раз из-за их параллельного выполнения, получая

$${\displaystyle T_{\infty }^{\text{sort}}(n)=T_{\infty }^{\text{sort}}\left({\frac {n}{2}}\right)+T_{\infty }^{\text{merge}}(n)=T_{\infty }^{\text{sort}}\left({\frac {n}{2}}\right)+\Theta \left(\log(n)^{2}\right).}$$

Подробную информацию о сложности процедуры параллельного слияния см. в разделе Алгоритм слияния .

Решение этого повторения дается формулой

$${\displaystyle T_{\infty }^{\text{sort}}=\Theta \left(\log(n)^{3}\right).}$$

Этот параллельный алгоритм слияния достигает параллелизма , что намного выше параллелизма предыдущего алгоритма. Такая сортировка может хорошо работать на практике, если сочетать ее с быстрой стабильной последовательной сортировкой, такой как сортировка вставкой , и быстрым последовательным слиянием в качестве базового случая для слияния небольших массивов. ^[20] ${\textstyle \Theta \left({\frac {n}{(\log n)^{2}}}\right)}$

Параллельная многоходовая сортировка слиянием

Кажется произвольным ограничивать алгоритмы сортировки слиянием методом бинарного слияния, поскольку обычно доступно p > 2 процессоров. Лучшим подходом может быть использование метода слияния K-way , обобщения бинарного слияния, в котором отсортированные последовательности объединяются. Этот вариант слияния хорошо подходит для описания алгоритма сортировки на PRAM . ^{[21] [22]} ${\displaystyle k}$

Основная идея

Параллельный многоходовой процесс сортировки слиянием на четырех процессорах . ${\displaystyle t_{0}}$ ${\displaystyle t_{3}}$

Учитывая неотсортированную последовательность элементов, цель состоит в том, чтобы отсортировать последовательность с доступными процессорами . Эти элементы распределяются равномерно между всеми процессорами и сортируются локально с использованием последовательного алгоритма сортировки . Следовательно, последовательность состоит из отсортированных последовательностей длины . Для упрощения пусть будет кратным , так что для . ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle S_{1},...,S_{p}}$ ${\textstyle \lceil {\frac {n}{p}}\rceil }$ ${\displaystyle n}$ ${\displaystyle p}$ ${\textstyle \left\vert S_{i}\right\vert ={\frac {n}{p}}}$ ${\displaystyle i=1,...,p}$

Эти последовательности будут использоваться для выполнения выбора мультипоследовательности/выбора разделителя. Для алгоритм определяет элементы разделителя с глобальным рангом . Затем соответствующие позиции в каждой последовательности определяются с помощью бинарного поиска и, таким образом, далее разбиваются на подпоследовательности с . ${\displaystyle j=1,...,p}$ ${\displaystyle v_{j}}$ ${\textstyle k=j{\frac {n}{p}}}$ ${\displaystyle v_{1},...,v_{p}}$ ${\displaystyle S_{i}}$ ${\displaystyle S_{i}}$ ${\displaystyle p}$ ${\displaystyle S_{i,1},...,S_{i,p}}$ ${\textstyle S_{i,j}:=\{x\in S_{i}|rank(v_{j-1})<rank(x)\leq rank(v_{j})\}}$

Кроме того, элементы назначаются процессору , то есть все элементы между рангом и рангом , которые распределены по всем . Таким образом, каждый процессор получает последовательность отсортированных последовательностей. Тот факт, что ранг элементов-разделителей был выбран глобально, обеспечивает два важных свойства: с одной стороны, был выбран таким образом, чтобы каждый процессор мог по-прежнему работать с элементами после назначения. Алгоритм идеально сбалансирован по нагрузке . С другой стороны, все элементы на процессоре меньше или равны всем элементам на процессоре . Следовательно, каждый процессор выполняет p -way merge локально и, таким образом, получает отсортированную последовательность из своих подпоследовательностей. Из-за второго свойства не нужно выполнять никаких дополнительных p -way-merge, результаты нужно только объединить в порядке номера процессора. ${\displaystyle S_{1,i},...,S_{p,i}}$ ${\displaystyle i}$ ${\textstyle (i-1){\frac {n}{p}}}$ ${\textstyle i{\frac {n}{p}}}$ ${\displaystyle S_{i}}$ ${\displaystyle k}$ ${\displaystyle v_{i}}$ ${\displaystyle k}$ ${\textstyle n/p}$ ${\displaystyle i}$ ${\displaystyle i+1}$

Многопоследовательный выбор

В простейшей форме, учитывая отсортированные последовательности, равномерно распределенные по процессорам, и ранг , задача состоит в том, чтобы найти элемент с глобальным рангом в объединении последовательностей. Следовательно, это можно использовать для разделения каждой из них на две части по индексу разделителя , где нижняя часть содержит только элементы, которые меньше , в то время как элементы, большие , расположены в верхней части. ${\displaystyle p}$ ${\displaystyle S_{1},...,S_{p}}$ ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle x}$ ${\displaystyle k}$ ${\displaystyle S_{i}}$ ${\displaystyle l_{i}}$ ${\displaystyle x}$ ${\displaystyle x}$

Представленный последовательный алгоритм возвращает индексы разделений в каждой последовательности, например, индексы в последовательностях , имеющих глобальный ранг меньше и . ^[23] ${\displaystyle l_{i}}$ ${\displaystyle S_{i}}$ ${\displaystyle S_{i}[l_{i}]}$ ${\displaystyle k}$ ${\displaystyle \mathrm {rank} \left(S_{i}[l_{i}+1]\right)\geq k}$

алгоритм msSelect(S : Массив отсортированных последовательностей [S_1,..,S_p], k : int) для i = 1 до p do (l_i, r_i) = (0, |S_i|-1) пока существует i: l_i < r_i делать// выбрать элемент Pivot в S_j[l_j], .., S_j[r_j], выбрать случайный j равномерноv := pickPivot(S, l, r)для i = 1 до p сделать  m_i = binarySearch(v, S_i[l_i, r_i]) // последовательноесли m_1 + ... + m_p >= k , то // m_1+ ... + m_p — глобальный ранг v r := m // векторное назначениееще л := м вернуться л

Для анализа сложности выбрана модель PRAM . Если данные равномерно распределены по всем , p-кратное выполнение метода binarySearch имеет время выполнения . Ожидаемая глубина рекурсии такая же, как в обычном Quickselect . Таким образом, общее ожидаемое время выполнения составляет . ${\displaystyle p}$ ${\displaystyle {\mathcal {O}}\left(p\log \left(n/p\right)\right)}$ ${\displaystyle {\mathcal {O}}\left(\log \left(\textstyle \sum _{i}|S_{i}|\right)\right)={\mathcal {O}}(\log(n))}$ ${\displaystyle {\mathcal {O}}\left(p\log(n/p)\log(n)\right)}$

Примененный к параллельной многоканальной сортировке слиянием, этот алгоритм должен быть вызван параллельно, так что все элементы-разделители ранга для будут найдены одновременно. Затем эти элементы-разделители могут быть использованы для разбиения каждой последовательности на части с тем же общим временем выполнения . ${\textstyle i{\frac {n}{p}}}$ ${\displaystyle i=1,..,p}$ ${\displaystyle p}$ ${\displaystyle {\mathcal {O}}\left(p\,\log(n/p)\log(n)\right)}$

Псевдокод

Ниже приведен полный псевдокод алгоритма параллельной многоканальной сортировки слиянием. Мы предполагаем, что существует барьерная синхронизация до и после выбора многопоследовательности, так что каждый процессор может правильно определить элементы разделения и раздел последовательности.

/** * d: Несортированный массив элементов * n: Количество элементов * p: Количество процессоров * вернуть отсортированный массив */алгоритм parallelMultiwayMergesort(d : Array, n : int, p : int) is o := new Array[0, n] // выходной массив для i = 1 до p выполняется параллельно // каждый процессор параллельно S_i := d[(i-1) * n/p, i * n/p] // Последовательность длины n/psort(S_i) // сортировка локально синхронизироватьv_i := msSelect([S_1,...,S_p], i * n/p) // элемент с глобальным рангом i * n/p синхронизировать(S_i,1, ..., S_i,p) := sequence_partitioning(si, v_1, ..., v_p) // разбить s_i на подпоследовательности o[(i-1) * n/p, i * n/p] := kWayMerge(s_1,i, ..., s_p,i) // объединить и присвоить выходному массиву вернуться о

Анализ

Во-первых, каждый процессор локально сортирует назначенные элементы, используя алгоритм сортировки со сложностью . После этого элементы разделителя должны быть рассчитаны за время . Наконец, каждая группа разделителей должна быть объединена параллельно каждым процессором со временем выполнения с использованием последовательного алгоритма слияния p-way . Таким образом, общее время выполнения определяется как ${\displaystyle n/p}$ ${\displaystyle {\mathcal {O}}\left(n/p\;\log(n/p)\right)}$ ${\displaystyle {\mathcal {O}}\left(p\,\log(n/p)\log(n)\right)}$ ${\displaystyle p}$ ${\displaystyle {\mathcal {O}}(\log(p)\;n/p)}$

${\displaystyle {\mathcal {O}}\left({\frac {n}{p}}\log \left({\frac {n}{p}}\right)+p\log \left({\frac {n}{p}}\right)\log(n)+{\frac {n}{p}}\log(p)\right)}$.

Практическая адаптация и применение

Алгоритм многоканальной сортировки слиянием очень масштабируем благодаря своей высокой способности к параллелизации, что позволяет использовать много процессоров. Это делает алгоритм жизнеспособным кандидатом для сортировки больших объемов данных, таких как те, которые обрабатываются в компьютерных кластерах . Кроме того, поскольку в таких системах память обычно не является ограничивающим ресурсом, недостаток сложности пространства сортировки слиянием незначителен. Однако в таких системах становятся важными другие факторы, которые не учитываются при моделировании на PRAM . Здесь необходимо учитывать следующие аспекты: Иерархия памяти , когда данные не помещаются в кэш процессоров, или накладные расходы на обмен данными между процессорами, которые могут стать узким местом, когда к данным больше нельзя получить доступ через общую память.

Сандерс и др. представили в своей статье синхронный параллельный алгоритм для многоуровневой многоканальной сортировки слиянием, который делит процессоры на группы размером . Все процессоры сначала сортируют локально. В отличие от одноуровневой многоканальной сортировки слиянием, эти последовательности затем разделяются на части и назначаются соответствующим группам процессоров. Эти шаги повторяются рекурсивно в этих группах. Это уменьшает коммуникацию и, в частности, позволяет избежать проблем с множеством небольших сообщений. Иерархическая структура базовой реальной сети может использоваться для определения групп процессоров (например, стоек , кластеров ,...). ^[22] ${\displaystyle p}$ ${\displaystyle r}$ ${\displaystyle p'}$ ${\displaystyle r}$

Другие варианты

Сортировка слиянием была одним из первых алгоритмов сортировки, где было достигнуто оптимальное ускорение, с Ричардом Коулом, использовавшим умный алгоритм подвыборки для обеспечения слияния O (1). ^[24] Другие сложные параллельные алгоритмы сортировки могут достигать тех же или лучших временных границ с меньшей константой. Например, в 1991 году Дэвид Пауэрс описал параллельную быструю сортировку (и связанную с ней радиксную сортировку ), которая может работать за время O (log n ) на параллельной машине с произвольным доступом (PRAM) CRCW с n процессорами, выполняя неявное разбиение. ^{[25] Пауэрс далее показывает, что конвейерная версия} битонической слияния Батчера за время O ((log n ) ^{2 ) на} сети сортировки бабочкой на практике фактически быстрее, чем его сортировки O (log n ) на PRAM, и он приводит подробное обсуждение скрытых накладных расходов в сравнении, радиксной и параллельной сортировки. ^[26]

Сравнение с другими алгоритмами сортировки

Хотя пирамидальная сортировка имеет те же временные ограничения, что и сортировка слиянием, она требует только Θ(1) вспомогательного пространства вместо Θ( n ) сортировки слиянием. На типичных современных архитектурах эффективные реализации быстрой сортировки обычно превосходят сортировку слиянием для сортировки массивов на основе ОЗУ. ^[27] Быстрая сортировка предпочтительна, когда размер сортируемых данных меньше, поскольку сложность пространства для быстрой сортировки составляет O(log n ), она помогает лучше использовать локальность кэша, чем сортировка слиянием (со сложностью пространства O(n)). ^[27] С другой стороны, сортировка слиянием является стабильной сортировкой и более эффективна при обработке последовательных носителей с медленным доступом. Сортировка слиянием часто является наилучшим выбором для сортировки связанного списка : в этой ситуации сравнительно легко реализовать сортировку слиянием таким образом, что для нее потребуется всего лишь Θ(1) дополнительного пространства, а медленная производительность случайного доступа связанного списка делает некоторые другие алгоритмы (например, быструю сортировку) плохо работающими, а другие (например, пирамидальную сортировку) вообще невозможными.

Начиная с Perl 5.8, сортировка слиянием является алгоритмом сортировки по умолчанию (в предыдущих версиях Perl это была быстрая сортировка). ^[28] В Java методы Arrays.sort() используют сортировку слиянием или настроенную быструю сортировку в зависимости от типов данных, а для эффективности реализации переключаются на сортировку вставкой, когда сортируется менее семи элементов массива. ^[29] Ядро Linux использует сортировку слиянием для своих связанных списков. ^[30]

Timsort , настроенный гибрид сортировки слиянием и сортировки вставкой, используется в различных программных платформах и языках, включая платформы Java и Android ^[31] и используется в Python с версии 2.3; с версии 3.11 политика слияния Timsort была обновлена ​​до Powersort. ^[32]

Ссылки

1. Скиена (2008, стр. 122)
2. Гудрич, Майкл Т.; Тамассиа, Роберто; Голдвассер, Майкл Х. (2013). "Глава 12 - Сортировка и выбор". Структуры данных и алгоритмы в Python (1-е изд.). Хобокен [Нью-Джерси]: Wiley. стр. 538–549. ISBN 978-1-118-29027-9.
3. Кнут (1998, стр. 158)
4. Катаяйнен, Юрки; Трефф, Йеспер Ларссон (март 1997 г.). «Алгоритмы и сложность». Труды 3-й Итальянской конференции по алгоритмам и сложности . Итальянская конференция по алгоритмам и сложности. Заметки лекций по информатике. Том 1203. Рим. С. 217–228. CiteSeerX 10.1.1.86.3154 . doi :10.1007/3-540-62592-5_74. ISBN  978-3-540-62592-6.
5. Кормен и др. (2009, стр. 36)
6. Приведенное здесь число для худшего случая не согласуется с приведенным в книге Кнута «Искусство программирования» , том 3. Расхождение возникает из-за того, что Кнут анализирует вариант реализации сортировки слиянием, которая немного неоптимальна.
7. Jayalakshmi, N. (2007). Структура данных с использованием C++. Firewall Media. ISBN 978-81-318-0020-1. OCLC  849900742.
8. Кормен и др. (2009, стр. 151)
9. Powers, David MW; McMahon, Graham B. (1983). "Сборник интересных программ на прологе". DCS Technical Report 8313 (Report). Кафедра компьютерных наук, Университет Нового Южного Уэльса.
10. "WikiSort. Быстрый и стабильный алгоритм сортировки, использующий O(1) памяти. Общественное достояние". GitHub . 14 апреля 2014 г.
11. Чандрамули, Бадриш; Голдштейн, Джонатан (2014). Терпение — добродетель: пересмотр слияния и сортировки на современных процессорах (PDF) . SIGMOD/PODS.
12. "Quadsort — это устойчивая адаптивная сортировка слиянием без ветвлений". GitHub . 8 июня 2022 г.
13. Катаджайнен, Пасанен и Теухола (1996)
14. Гефферт, Вильям; Катахайнен, Юрки; Пасанен, Томи (2000). «Асимптотически эффективное слияние на месте». Теоретическая информатика . 237 (1–2): 159–181. дои : 10.1016/S0304-3975(98)00162-5 .
15. Хуан, Бин-Чао; Лэнгстон, Майкл А. (март 1988 г.). «Практическое слияние на месте». Сообщения ACM . 31 (3): 348–352. doi : 10.1145/42392.42403 . S2CID  4841909.
16. Ким, Пок-Сон; Кутцнер, Арне (2004). «Стабильное минимальное слияние памяти с помощью симметричных сравнений». Алгоритмы – ESA 2004 . Европейский симпозиум. Алгоритмы. Заметки лекций по информатике. Том 3221. С. 714–723. CiteSeerX 10.1.1.102.4612 . doi :10.1007/978-3-540-30140-0_63. ISBN  978-3-540-23025-0.
17. Ким, Пок-Сон; Кутцнер, Арне (1 сентября 2003 г.). «Новый метод эффективного слияния на месте». Труды конференции Корейского института интеллектуальных систем : 392–394.
18. Феррагина, Паоло (2009–2019), «5. Сортировка атомарных элементов» (PDF) , Магия алгоритмов!, стр. 5-4, архивировано (PDF) из оригинала 2021-05-12
19. Кормен и др. (2009, стр. 797–805)
20. Виктор Дж. Дуваненко «Параллельная сортировка слиянием» Журнал и блог доктора Добба [1] и реализация C++ репозитория GitHub [2]
21. Питер Сандерс; Йоханнес Синглер (2008). «Лекция «Параллельные алгоритмы» (PDF) . Проверено 02 мая 2020 г.
22. Axtmann, Michael; Bingmann, Timo; Sanders, Peter; Schulz, Christian (2015). "Practical Massively Parallel Sorting". Труды 27-го симпозиума ACM по параллелизму в алгоритмах и архитектурах . стр. 13–23. doi :10.1145/2755573.2755595. ISBN 9781450335881. S2CID  18249978.
23. Питер Сандерс (2019). "Лекция Параллельные алгоритмы" (PDF) . Получено 2020-05-02 .
24. Коул, Ричард (август 1988 г.). «Параллельная сортировка слиянием». SIAM J. Comput . 17 (4): 770–785. CiteSeerX 10.1.1.464.7118 . doi :10.1137/0217049. S2CID  2416667. 
25. Powers, David MW (1991). "Parallelized Quicksort and Radixsort with Optimal Speedup". Труды Международной конференции по параллельным вычислительным технологиям, Новосибирск . Архивировано из оригинала 25-05-2007.
26. Powers, David MW (январь 1995). Parallel Unification: Practical Complexity (PDF) . Australasian Computer Architecture Workshop, Flinders University.
27. Oladipupo, Esau Taiwo; Abikoye, Oluwakemi Christianah (2020). "Сравнение быстрой сортировки и сортировки слиянием". Третья международная конференция по вычислениям и сетевым коммуникациям (CoCoNet 2019) . 2020 (2020): 9. Получено 2024-01-20 – через Elsevier Science Direct.
28. "Sort – Perl 5 version 8.8 documentation" . Получено 2020-08-23 .
29. coleenp (22 февраля 2019 г.). "src/java.base/share/classes/java/util/Arrays.java @ 53904:9c3fe09f69bc". OpenJDK .
30. ядро ​​Linux /lib/list_sort.c
31. Ливерпульский университет (2022-12-12). «Ученые-компьютерщики улучшают функцию сортировки Python». Tech Xplore . Получено 2024-05-08 .
32. Джеймс, Майк (21.12.2022). «Python теперь использует Powersort». i-programmer.info . Получено 08.05.2024 .

Библиография

• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03384-4.
• Катаяйнен, Юрки; Пасанен, Томи; Теухола, Юкка (1996). «Практическая сортировка слиянием на месте». Nordic Journal of Computing . 3 (1): 27–40. CiteSeerX  10.1.1.22.8523 . ISSN  1236-6064. Архивировано из оригинала 2011-08-07 . Получено 2009-04-04 .. Также практическая сортировка слиянием на месте. Также [3]
• Кнут, Дональд (1998). "Раздел 5.2.4: Сортировка слиянием". Сортировка и поиск . Искусство программирования . Том 3 (2-е изд.). Эддисон-Уэсли. С. 158–168. ISBN 0-201-89685-0.
• Кронрод, М.А. (1969). «Оптимальный алгоритм упорядочения без операционного поля». Советская математика — Доклады АН СССР . 10 : 744.
• LaMarca, A.; Ladner, RE (1997). «Влияние кэшей на производительность сортировки». Proc. 8th Ann. ACM-SIAM Symp. On Discrete Algorithms (SODA97) : 370–379. CiteSeerX  10.1.1.31.1153 .
• Скиена, Стивен С. (2008). "4.5: Mergesort: Sorting by Divide-and-Conquer". The Algorithm Design Manual (2-е изд.). Springer. стр. 120–125. ISBN 978-1-84800-069-8.
• Sun Microsystems. "API массивов (Java SE 6)" . Получено 19.11.2007 .
• Oracle Corp. "Массивы (Java SE 10 и JDK 10)" . Получено 2018-07-23 .

Внешние ссылки

• Анимированные алгоритмы сортировки: сортировка слиянием на Wayback Machine (архив 6 марта 2015 г.) – графическая демонстрация
• Открытые структуры данных - Раздел 11.1.1 - Сортировка слиянием, Пэт Морин