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

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

Пример сортировки слиянием. Сначала разделите список на наименьшую единицу (1 элемент), затем сравните каждый элемент со смежным списком, чтобы отсортировать и объединить два соседних списка. Наконец все элементы отсортированы и объединены.
Учебный класс	Алгоритм сортировки
Структура данных	Множество
Худший случай спектакль	${displaystyle O(nlog n)}$
Лучший случай спектакль	${displaystyle Omega (nlog n)}$ типичный,${displaystyle Omega (n)}$ естественный вариант
Средний спектакль	${displaystyle Theta (nlog n)}$
Худший случай космическая сложность	${displaystyle O(n)}$ всего с ${displaystyle O(n)}$ вспомогательный, ${displaystyle O(1)}$ вспомогательный со связанными списками[1]

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

Алгоритм

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

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

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

Пример C-подобный код, использующий индексы для алгоритма сортировки слиянием сверху вниз, который рекурсивно разбивает список (называемый бежит в этом примере) в подсписки, пока размер подсписка не станет равным 1, затем объединяет эти подсписки для создания отсортированного списка. Шага обратного копирования избегается за счет чередования направления слияния с каждым уровнем рекурсии (за исключением первоначального одноразового копирования). Чтобы понять это, рассмотрим массив из 2 элементов. Элементы копируются в B [], затем снова объединяются в A []. Если есть 4 элемента, когда достигается нижний предел уровня рекурсии, отдельные элементы, выполняемые из A [], объединяются с B [], а затем на следующем более высоком уровне рекурсии эти два выполнения элементов объединяются с A []. Этот шаблон продолжается на каждом уровне рекурсии.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Начало: 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)

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

Анализ

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

В сортировке п объекты, сортировка слиянием имеет средний и худшая производительность из О (п бревноп). Если время выполнения сортировки слиянием для списка длины п является Т(п), то повторение Т(п) = 2Т(п/2) + п следует из определения алгоритма (применить алгоритм к двум спискам половинного размера исходного списка и добавить п шаги, предпринятые для объединения двух полученных списков). Замкнутая форма следует из основная теорема для повторений "разделяй и властвуй".

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

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

в наихудший случае сортировка слиянием выполняет примерно на 39% меньше сравнений, чем быстрая сортировка делает в средний дело. С точки зрения ходов сложность наихудшего случая сортировки слиянием равна О (п бревноп) - та же сложность, что и лучший случай быстрой сортировки, а лучший случай сортировки слиянием занимает примерно половину итераций, чем худший случай.^{[нужна цитата ]}

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

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

Варианты

Варианты сортировки слиянием в первую очередь связаны с уменьшением сложности пространства и стоимости копирования.

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

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

• Катаянен и другие. представить алгоритм, который требует постоянного объема рабочей памяти: достаточно места для хранения одного элемента входного массива и дополнительного пространства для хранения О(1) указатели на входной массив. Они достигают О(п бревно п) временные ограничения с небольшими константами, но их алгоритм нестабилен.^[7]
• Было предпринято несколько попыток создания слияние на месте алгоритм, который можно комбинировать со стандартной (нисходящей или восходящей) сортировкой слиянием для создания сортировки слиянием на месте. В этом случае понятие «на месте» может быть смягчено, чтобы означать «использование логарифмического пространства стека», потому что стандартная сортировка слиянием требует этого количества пространства для использования в собственном стеке. Это показал Гефферт и другие. что на месте возможно стабильное слияние в О(п бревно п) время, используя постоянный объем рабочего пространства, но их алгоритм сложен и имеет высокие постоянные коэффициенты: объединение массивов длины п и м может взять 5п + 12м + о(м) движется.^[8] Этот высокий постоянный коэффициент и сложный алгоритм на месте стал проще и понятнее. Бин-Чао Хуанг и Майкл А. Лэнгстон^[9] представил простой алгоритм линейного времени практическое слияние на месте для объединения отсортированного списка с использованием фиксированного количества дополнительного места. Оба они использовали работы Кронрода и других. Он сливается в линейное время и постоянное дополнительное пространство. Алгоритм занимает в среднем немного больше времени, чем стандартные алгоритмы сортировки слиянием, позволяя использовать O (n) временных дополнительных ячеек памяти менее чем в два раза. Хотя с практической точки зрения алгоритм намного быстрее, он также нестабилен для некоторых списков. Но, используя аналогичные концепции, они смогли решить эту проблему. Другие локальные алгоритмы включают SymMerge, который требует О((п + м) бревно (п + м)) время в целом и стабильно.^[10] Подключение такого алгоритма к сортировке слиянием увеличивает его сложность долинейный, но все равно квазилинейный, О(п (бревно п)²).
• Современное стабильное линейное слияние и слияние по месту - это блочная сортировка слиянием.

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

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

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

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

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

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

Вместо того, чтобы начинать с очень коротких пробежек, обычно гибридный алгоритм используется, когда начальный проход будет считывать множество записей в память, выполнять внутреннюю сортировку для создания длительного цикла, а затем распределять эти длинные прогоны по выходному набору. Шаг позволяет избежать многих ранних проходов. Например, внутренняя сортировка из 1024 записей сэкономит девять проходов. Внутренняя сортировка часто бывает большой, потому что она имеет такое преимущество. Фактически, есть методы, которые могут сделать начальные запуски дольше, чем доступная внутренняя память.^[11]

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

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

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

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

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

Кронрод (1969) предложил альтернативный вариант сортировки слиянием, который использует постоянное дополнительное пространство. Позднее этот алгоритм был усовершенствован. (Катаянен, Пасанен и Теухола 1996 )

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

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

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

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

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

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

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

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

Основная статья: Алгоритм слияния § Параллельное слияние

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

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

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

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

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

${ extstyle T_{infty }^{ ext{sort}}(n)=T_{infty }^{ ext{sort}}left({frac {n}{2}}ight)+T_{infty }^{ ext{merge}}(n)=T_{infty }^{ ext{sort}}left({frac {n}{2}}ight)+Theta left(log(n)^{2}ight)}$.

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

Решение этого повторения дается

${ extstyle T_{infty }^{ ext{sort}}=Theta left(log(n)^{3}ight)}$.

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

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

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

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

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

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

Эти последовательности будут использоваться для выполнения выбора последовательности / выбора разделителя. За ${displaystyle j=1,...,p}$, алгоритм определяет элементы разделителя ${displaystyle v_{j}}$ с мировым рейтингом ${ extstyle 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}}$ с ${ extstyle S_{i,j}:={xin S_{i}|rank(v_{j-1})<rank(x)leq rank(v_{j})}}$.

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

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

В простейшем виде, учитывая ${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}$ расположены в верхней части.

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

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

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

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

Псевдокод

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

/ ** * d: Несортированный массив элементов * n: Количество элементов * p: Количество процессоров * return Sorted Array * /алгоритм parallelMultiwayMergesort (d: массив, n: int, p: int) является    o: = новый Array [0, n] // выходной массив за я = 1 к п делать параллельно                // каждый процессор параллельно S_i: = d [(i-1) * n / p, i * n / p] // Последовательность длины n / p sort (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) // объединить и присвоить выходному массиву возвращаться о

Анализ

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

${displaystyle {mathcal {O}}left({frac {n}{p}}log left({frac {n}{p}}ight)+plog left({frac {n}{p}}ight)log(n)+{frac {n}{p}}log(p)ight)}$.

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

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

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

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

Сортировка слиянием была одним из первых алгоритмов сортировки, в которых была достигнута оптимальная скорость, а Ричард Коул использовал умный алгоритм подвыборки, чтобы гарантировать О(1) слияние.^[17] Другие сложные алгоритмы параллельной сортировки могут обеспечить такие же или лучшие временные границы с более низкой константой. Например, в 1991 году Дэвид Пауэрс описал распараллеливание быстрая сортировка (и связанный радиальная сортировка ), которые могут работать в О(бревно п) время на CRCW параллельная машина с произвольным доступом (PRAM) с п процессоров, выполняя неявное разделение.^[18] Пауэрс также показывает, что конвейерная версия Batcher Bitonic Mergesort в О((бревно п)²) время на бабочке сортировочная сеть на практике на самом деле быстрее, чем его О(бревно п) сортирует в PRAM, и он предоставляет подробное обсуждение скрытых накладных расходов при сравнении, поразрядной и параллельной сортировке.^[19]

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

Несмотря на то что heapsort имеет те же временные границы, что и сортировка слиянием, для нее требуется только вспомогательное пространство Θ (1) вместо сортировки слиянием Θ (п). На типичных современных архитектурах, эффективных быстрая сортировка реализации обычно превосходят сортировку слиянием для сортировки массивов на основе RAM.^{[нужна цитата ]} С другой стороны, сортировка слиянием является стабильной и более эффективной при обработке последовательных носителей с медленным доступом. Сортировка слиянием часто является лучшим выбором для сортировки связанный список: в этой ситуации относительно легко реализовать сортировку слиянием таким образом, что для этого требуется только Θ (1) дополнительного места, а медленная производительность произвольного доступа связанного списка делает некоторые другие алгоритмы (например, быструю сортировку) плохо работающими , и другие (например, heapsort) совершенно невозможно.

По состоянию на Perl 5.8, сортировка слиянием является его алгоритмом сортировки по умолчанию (в предыдущих версиях Perl это была быстрая сортировка).^[20] В Ява, то Arrays.sort () методы используют сортировку слиянием или настроенную быструю сортировку в зависимости от типов данных и для повышения эффективности реализации переключитесь на вставка сортировки когда сортируется менее семи элементов массива.^[21] В Linux ядро использует сортировку слиянием для своих связанных списков.^[22] Python использует Тимсорт, еще один настроенный гибрид сортировки слиянием и сортировки вставкой, который стал стандартным алгоритмом сортировки в Java SE 7 (для массивов непримитивных типов),^[23] на Платформа Android,^[24] И в GNU Octave.^[25]

Примечания

1. Скиена (2008), п. 122)
2. Кнут (1998), п. 158)
3. Катаянен, Юрки; Träff, Джеспер Ларссон (март 1997 г.). «Тщательный анализ программ сортировки слиянием» (PDF). Труды 3-й итальянской конференции по алгоритмам и сложности. Итальянская конференция по алгоритмам и сложности. Рим. С. 217–228. CiteSeerX  10.1.1.86.3154. Дои:10.1007/3-540-62592-5_74.
4. Пауэрс, Дэвид М. У .; МакМахон, Грэм Б. (1983). «Сборник интересных программ пролога». Технический отчет DCS 8313 (Отчет). Департамент компьютерных наук Университета Нового Южного Уэльса.
5. Приведенное здесь число наихудшего случая не согласуется с приведенным в Knuth с Искусство программирования, Том 3. Расхождение связано с тем, что Кнут анализирует вариант реализации сортировки слиянием, который немного неоптимален.
6. Cormen et al. (2009 г., п. 151) Ошибка harvtxt: цель отсутствует: CITEREFCormenLeisersonRivestStein2009 (помощь)
7. Катаянен, Пасанен и Теухола (1996)
8. Гефферт, Вильям; Катаянен, Юрки; Пасанен, Томи (2000). «Асимптотически эффективное слияние на месте». Теоретическая информатика. 237 (1–2): 159–181. Дои:10.1016 / S0304-3975 (98) 00162-5.
9. Хуанг, Бин-Чао; Лэнгстон, Майкл А. (март 1988 г.). «Практическое слияние на месте». Коммуникации ACM. 31 (3): 348–352. Дои:10.1145/42392.42403. S2CID  4841909.
10. Ким, Пок-Сон; Куцнер, Арне (2004). Стабильное слияние минимального объема памяти посредством симметричных сравнений. Европейский Symp. Алгоритмы. Конспект лекций по информатике. 3221. С. 714–723. CiteSeerX  10.1.1.102.4612. Дои:10.1007/978-3-540-30140-0_63. ISBN  978-3-540-23025-0.
11. Выборочная сортировка. Снегоочиститель Кнута. Естественное слияние.
12. Cormen et al. (2009 г., стр. 797–805). Ошибка harvtxt: цель отсутствует: CITEREFCormenLeisersonRivestStein2009 (помощь)
13. Виктор Дж. Дуваненко "Сортировка параллельным слиянием" Журнал и блог доктора Добба[1] и реализация репозитория GitHub на C ++ [2]
14. Питер Сандерс; Йоханнес Синглер (2008). "Лекция Параллельные алгоритмы" (PDF). Получено 2020-05-02.
15. Акстманн, Майкл; Бингманн, Тимо; Сандерс, Питер; Шульц, Кристиан (2015). «Практическая массовая параллельная сортировка». Материалы 27-го симпозиума ACM по параллелизму в алгоритмах и архитектурах: 13–23. Дои:10.1145/2755573.2755595. ISBN  9781450335881. S2CID  18249978.
16. Питер Сандерс (2019). "Лекция Параллельные алгоритмы" (PDF). Получено 2020-05-02.
17. Коул, Ричард (август 1988 г.). «Сортировка с параллельным слиянием». SIAM J. Comput. 17 (4): 770–785. CiteSeerX  10.1.1.464.7118. Дои:10.1137/0217049. S2CID  2416667.
18. Пауэрс, Дэвид М. В. (1991). «Параллельная быстрая и радиксная сортировка с оптимальным ускорением». Материалы Международной конференции по параллельным вычислительным технологиям, Новосибирск. Архивировано из оригинал на 2007-05-25.
19. Пауэрс, Дэвид М. В. (январь 1995 г.). Параллельное объединение: практическая сложность (PDF). Австралийский семинар по компьютерной архитектуре Университет Флиндерса.
20. «Сортировка - документация Perl 5 версии 8.8». Получено 2020-08-23.
21. coleenp (22 фев 2019). "src / java.base / share / classes / java / util / Arrays.java @ 53904: 9c3fe09f69bc". OpenJDK.
22. ядро linux /lib/list_sort.c
23. jjb (29 июля 2009 г.). «Фиксировать 6804124: заменить« модифицированную сортировку слиянием »в java.util.Arrays.sort на timsort». Репозиторий Java Development Kit 7 Hg. В архиве из оригинала на 2018-01-26. Получено 24 февраля 2011.
24. "Класс: java.util.TimSort ". Документация Android JDK. Архивировано из оригинал 20 января 2015 г.. Получено 19 янв 2015.
25. "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. Архивировано из оригинал на 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 .; Ладнер, Р. Э. (1997). «Влияние кешей на производительность сортировки». Proc. 8-я Ann. ACM-SIAM Symp. О дискретных алгоритмах (SODA97): 370–379. CiteSeerX  10.1.1.31.1153.
• Скиена, Стивен С. (2008). «4.5: Сортировка слиянием: сортировка по принципу« разделяй и властвуй »». Руководство по разработке алгоритмов (2-е изд.). Springer. С. 120–125. ISBN  978-1-84800-069-8.
• Sun Microsystems. "Arrays API (Java SE 6)". Получено 2007-11-19.
• Oracle Corp. «Массивы (Java SE 10 и JDK 10)». Получено 2018-07-23.

внешняя ссылка

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