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

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

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

Алгоритм

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

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 []) { я = iBegin , j = iMiddle ; // Пока в левом или правом проходе есть элементы... for ( k = iBegin ; k < iEnd ; k ++ ) { // Если левый заголовок существует и <= существующий правый заголовок. if ( i < iMiddle && ( j >= iEnd || A [ i ] <= A [ j ])) { B [ k ] = A [ i ]); я знак равно я + 1 ; } Еще { 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[] содержит элементы для сортировки; array 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 * ширина , n ), B ); } // Теперь рабочий массив B полон фрагментов длиной 2*ширина. // Копируем массив B в массив A для следующей итерации. // Более эффективная реализация поменяла бы роли A и B. CopyArray ( B , A , n ); // Теперь массив A полон фрагментов длиной 2*ширина. } }                                                    // Левый ход — A[iLeft :iRight-1]. // Пробег вправо — A[iRight:iEnd-1]. void BottomUpMerge ( A [], iLeft , iRight , iEnd , B []) { я = iLeft , j = iRight ; // Пока есть элементы в левом или правом проходах... for ( k = iLeft ; k < iEnd ; k ++ ) { // Если левый заголовок существует и <= существующий правый заголовок. if ( i < iRight && ( j >= iEnd || A [ i ] <= A [ j ])) { B [ k ] = A [ i ]; я знак равно я + 1 ; } Еще { B [ k ] = A [ j ]; j = j + 1 ; } } }                                                          void CopyArray ( B [], A [], n ) { for ( я знак равно 0 ; я < n ; я ++ ) A [ я ] = B [ я ]; }              

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

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

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

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

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

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

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

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

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

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

merge_sort :: [ a ] ​​-> [ a ] ​​merge_sort ( [] ) = [] merge_sort ([ x ]) = [ x ] merge_sort ( xs ) = merge ( merge_sort ( left ), merge_sort ( right )) где ( left , вправо ) = разделение ( xs , длина ( xs ) / 2 ) слияние :: ([ a ], [ a ]) -> [ a ] ​​слияние ( [] , xs ) = xs слияние ( xs , [] ) = xs слияние ( Икс : Икс , y : ys ) | если Икс ≤ y знак равно Икс : объединить ( xs , y : ys ) | еще = y : объединить ( x : xs , ys )                                                          

Анализ

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

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

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

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

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

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

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

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

Естественная сортировка слиянием аналогична сортировке слиянием снизу вверх, за исключением того, что во входных данных используются любые естественные серии (отсортированные последовательности). Могут быть использованы как монотонные, так и битонные (попеременные вверх/вниз) прогоны, при этом списки (или, что эквивалентно, ленты или файлы) являются удобными структурами данных (используются в качестве очередей FIFO или стеков LIFO ). ^[8] При сортировке слиянием снизу вверх исходная точка предполагает, что каждая серия имеет длину один элемент. На практике случайные входные данные будут иметь множество коротких периодов, которые просто сортируются. В типичном случае естественная сортировка слиянием может не требовать такого количества проходов, поскольку требуется меньшее количество проходов для слияния. В лучшем случае входные данные уже отсортированы (т. е. выполнены за один проход), поэтому для естественной сортировки слиянием достаточно выполнить только один проход по данным. Во многих практических случаях присутствуют длинные естественные прогоны, и по этой причине естественная сортировка слиянием используется как ключевой компонент 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 году. Позже в том же году этот метод был описан как оптимизация для терпеливой сортировки и назван слиянием «пинг-понг». ^{[9] [10]} Quadsort реализовала этот метод в 2020 году и назвала его четырехкратным слиянием. ^[11]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Чтобы проанализировать рекуррентное отношение для наихудшего случая, рекурсивные вызовы 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).}$$

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

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

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

Представленный последовательный алгоритм возвращает индексы разбиений в каждой последовательности, например, индексы в последовательностях , имеющих глобальный ранг меньше и . ^[22] ${\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) пока существует я: l_i < r_i do// выбираем опорный элемент в S_j[l_j], .., S_j[r_j], равномерно выбираем случайный jv := 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 . Если данные равномерно распределены по всем , время выполнения методаbinarySearch в p-кратном порядке составляет . Ожидаемая глубина рекурсии такая же, как и в обычном 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)}$

Применительно к параллельной многосторонней сортировке слиянием этот алгоритм должен вызываться параллельно, чтобы все элементы разделителя ранга for находились одновременно. Эти элементы-разделители затем можно использовать для разделения каждой последовательности на части с одинаковым общим временем выполнения . ${\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: количество процессоров * вернуть отсортированный массив */алгоритм параллельныйMultiwayMergesort(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] := кВтayMerge(s_1,i, ..., s_p,i) // объединяем и присваиваем выходному массиву вернуться о

Анализ

Во-первых, каждый процессор сортирует назначенные элементы локально, используя алгоритм сортировки со сложностью . После этого элементы разветвителя необходимо рассчитать по времени . Наконец, каждая группа разделений должна быть объединена параллельно каждым процессором с использованием последовательного алгоритма p-путевого слияния . Таким образом, общее время работы определяется выражением ${\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 . Здесь необходимо учитывать следующие аспекты: Иерархия памяти , когда данные не помещаются в кэш процессоров, или накладные расходы на обмен данными между процессорами, которые могут стать узким местом, когда к данным больше нельзя получить доступ через общий доступ. Память.

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

Дальнейшие варианты

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

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

Хотя пирамидальная сортировка имеет те же временные ограничения, что и сортировка слиянием, для нее требуется только вспомогательное пространство Θ(1) вместо Θ( n ) сортировки слиянием . В типичных современных архитектурах эффективные реализации быстрой сортировки обычно превосходят сортировку слиянием для сортировки массивов в оперативной памяти. ^{[ нужна цитата ] [26]} Быстрая сортировка предпочтительна, когда размер сортируемых данных меньше, поскольку сложность пространства для быстрой сортировки равна O(logn), это помогает использовать локальность кэша лучше, чем сортировка слиянием (со сложностью пространства O(n) ). ^[26] С другой стороны, сортировка слиянием является стабильной сортировкой и более эффективна при обработке последовательных носителей с медленным доступом. Сортировка слиянием часто является лучшим выбором для сортировки связанного списка : в этой ситуации относительно легко реализовать сортировку слиянием таким образом, чтобы для нее требовалось всего Θ(1) дополнительного пространства и медленная производительность связанного списка при произвольном доступе. list приводит к тому, что некоторые другие алгоритмы (например, быстрая сортировка) работают плохо, а другие (например, пирамидальная сортировка) становятся совершенно невозможными.

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

Примечания

1. Скиена (2008, стр. 122)
2. Кнут (1998, стр. 158)
3. Катаджайнен, Юрки; Трефф, Йеспер Ларссон (март 1997 г.). «Алгоритмы и сложность». Материалы 3-й итальянской конференции по алгоритмам и сложности . Итальянская конференция по алгоритмам и сложности. Конспекты лекций по информатике. Том. 1203. Рим. стр. 217–228. CiteSeerX  10.1.1.86.3154 . дои : 10.1007/3-540-62592-5_74. ISBN 978-3-540-62592-6.
4. Кормен и др. (2009, стр. 36)
5. Наихудшее число, приведенное здесь, не совпадает с числом, данным в « Искусстве компьютерного программирования» Кнута , том 3 . Расхождение связано с тем, что Кнут анализировал вариант реализации сортировки слиянием, который немного неоптимален.
6. Джаялакшми, Н. (2007). Структура данных с использованием C++. Брандмауэр Медиа. ISBN 978-81-318-0020-1. ОСЛК  849900742.
7. Кормен и др. (2009, стр. 151)
8. Пауэрс, Дэвид М.В.; МакМахон, Грэм Б. (1983). «Сборник интересных программ на прологе». Технический отчет DCS 8313 (Отчет). Департамент компьютерных наук Университета Нового Южного Уэльса.
9. «WikiSort. Быстрый и стабильный алгоритм сортировки, использующий память O (1). Общественное достояние». Гитхаб . 14 апреля 2014 г.
10. Чандрамули, Бадриш; Гольдштейн, Джонатан (2014). Терпение — добродетель: новый взгляд на слияние и сортировку на современных процессорах (PDF) . СИГМОД/ПОДС.
11. «Quadsort — это стабильная адаптивная сортировка слиянием без ветвей». Гитхаб . 8 июня 2022 г.
12. Катаджайнен, Пасанен и Теухола (1996)
13. Гефферт, Вильям; Катахайнен, Юрки; Пасанен, Томи (2000). «Асимптотически эффективное слияние на месте». Теоретическая информатика . 237 (1–2): 159–181. дои : 10.1016/S0304-3975(98)00162-5 .
14. Хуан, Бин-Чао; Лэнгстон, Майкл А. (март 1988 г.). «Практическое слияние на месте». Коммуникации АКМ . 31 (3): 348–352. дои : 10.1145/42392.42403 . S2CID  4841909.
15. Ким, Пок-Сон; Куцнер, Арне (2004). «Слияние стабильного минимального объема памяти путем симметричных сравнений». Алгоритмы – ЕКА 2004 . Европейский симп. Алгоритмы. Конспекты лекций по информатике. Том. 3221. стр. 714–723. CiteSeerX 10.1.1.102.4612 . дои : 10.1007/978-3-540-30140-0_63. ISBN  978-3-540-23025-0.
16. Ким, Пок-Сон; Куцнер, Арне (1 сентября 2003 г.). «Новый метод эффективного слияния на месте». Материалы конференции Корейского института интеллектуальных систем : 392–394.
17. Феррагина, Паоло (2009–2019), «5. Сортировка атомарных элементов» (PDF) , Магия алгоритмов! , п. 5-4, заархивировано (PDF) из оригинала 12 мая 2021 г.
18. Кормен и др. (2009, стр. 797–805)
19. Виктор Дж. Дуваненко «Параллельная сортировка слиянием» Журнал и блог доктора Добба [1] и реализация C++ репозитория GitHub [2]
20. Питер Сандерс; Йоханнес Синглер (2008). «Лекция «Параллельные алгоритмы» (PDF) . Проверено 2 мая 2020 г.
21. Акстманн, Майкл; Бингманн, Тимо; Сандерс, Питер; Шульц, Кристиан (2015). «Практическая массово-параллельная сортировка». Материалы 27-го симпозиума ACM по параллелизму в алгоритмах и архитектурах . стр. 13–23. дои : 10.1145/2755573.2755595. ISBN 9781450335881. S2CID  18249978.
22. Питер Сандерс (2019). «Лекция «Параллельные алгоритмы» (PDF) . Проверено 2 мая 2020 г.
23. Коул, Ричард (август 1988 г.). «Параллельная сортировка слиянием». СИАМ Дж. Компьютер . 17 (4): 770–785. CiteSeerX 10.1.1.464.7118 . дои : 10.1137/0217049. S2CID  2416667. 
24. Пауэрс, Дэвид М.В. (1991). «Параллельная быстрая сортировка и поразрядная сортировка с оптимальным ускорением». Материалы международной конференции по параллельным вычислительным технологиям, Новосибирск . Архивировано из оригинала 25 мая 2007 г.
25. Пауэрс, Дэвид М.В. (январь 1995 г.). Параллельная унификация: практическая сложность (PDF) . Австралазийский семинар по компьютерной архитектуре Университета Флиндерса.
26. Оладипупо, Исав Тайво; Абойе, Олувакеми Кристиана (20 января 2024 г.). «Сравнение быстрой сортировки и сортировки слиянием». Наука-прямая . 2020 (2020): 9 – через Elsevier Science Direct.
27. «Сортировка – документация Perl 5 версии 8.8» . Проверено 23 августа 2020 г.
28. Колинп (22 февраля 2019 г.). «src/java.base/share/classes/java/util/Arrays.java @ 53904:9c3fe09f69bc». OpenJDK .
29. ядро ​​Linux /lib/list_sort.c
30. jjb (29 июля 2009 г.). «Коммит 6804124: заменить «модифицированную сортировку слиянием» в java.util.Arrays.sort на timsort». Репозиторий Java Development Kit 7 Hg . Архивировано из оригинала 26 января 2018 г. Проверено 24 февраля 2011 г.
31. "Класс: java.util.TimSort<T>". Документация Android JDK . Архивировано из оригинала 20 января 2015 года . Проверено 19 января 2015 г.
32. "liboctave/util/oct-sort.cc". Репозиторий Mercurial исходного кода Octave . Строки 23-25 ​​начального блока комментариев . Проверено 18 февраля 2013 г. Код, по большей части украденный из Python, listobject.c, который сам по себе не имел заголовка лицензии. Однако спасибо Тиму Питерсу за те части кода, которые я украл.

Рекомендации

• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03384-4.
• Катахайнен, Юрки; Пасанен, Томи; Теухола, Юкка (1996). «Практическая сортировка слиянием на месте». Северный журнал вычислительной техники . 3 (1): 27–40. CiteSeerX  10.1.1.22.8523 . ISSN  1236-6064. Архивировано из оригинала 7 августа 2011 г. Проверено 4 апреля 2009 г.. Также практичная сортировка слиянием на месте. Также [3]
• Кнут, Дональд (1998). «Раздел 5.2.4: Сортировка путем слияния». Сортировка и поиск . Искусство компьютерного программирования . Том. 3 (2-е изд.). Аддисон-Уэсли. стр. 158–168. ISBN 0-201-89685-0.
• Кронрод, Массачусетс (1969). «Алгоритм оптимального упорядочения без операционного поля». Советская математика — Доклады . 10 :744.
• ЛаМарка, А.; Ладнер, Р.Э. (1997). «Влияние кешей на производительность сортировки». Учеб. 8-я Энн. Симпозиум ACM-SIAM. О дискретных алгоритмах (SODA97) : 370–379. CiteSeerX  10.1.1.31.1153 .
• Скиена, Стивен С. (2008). «4.5: Сортировка слиянием: сортировка по принципу «разделяй и властвуй». Руководство по разработке алгоритмов (2-е изд.). Спрингер. стр. 120–125. ISBN 978-1-84800-069-8.
• Сан Микросистемс. «API массивов (Java SE 6)» . Проверено 19 ноября 2007 г.
• Oracle Corp. «Массивы (Java SE 10 и JDK 10)» . Проверено 23 июля 2018 г.

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

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