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

Эта статья, возможно, содержит оригинальные исследования . Пожалуйста, улучшите его , проверив сделанные утверждения и добавив встроенные цитаты . Заявления, содержащие только оригинальные исследования, следует удалить. ( Май 2016 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

Алгоритм [ править ]

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

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

Реализация сверху вниз [ править ]

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

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

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

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

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

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

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

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

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

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

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

Сортировка естественным слиянием похожа на сортировку слиянием снизу вверх, за исключением того, что используются любые естественные прогоны (отсортированные последовательности) во входных данных. Могут использоваться как монотонный, так и битонный (чередующийся вверх / вниз) прогоны, при этом списки (или эквивалентные ленты или файлы) являются удобными структурами данных (используемыми как очереди FIFO или стеки LIFO ). ^[4]При сортировке слиянием снизу вверх начальная точка предполагает, что каждый запуск состоит из одного элемента. На практике случайные входные данные будут иметь много коротких прогонов, которые просто необходимо отсортировать. В типичном случае для естественной сортировки слиянием может не потребоваться такое количество проходов, потому что для слияния требуется меньше запусков. В лучшем случае входные данные уже отсортированы (т. Е. Выполняется за один проход), поэтому при естественной сортировке слиянием требуется только один проход через данные. Во многих практических случаях присутствуют длинные естественные прогоны, и по этой причине естественная сортировка слиянием используется как ключевой компонент 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)

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

Анализ [ править ]

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

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

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

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

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

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

Варианты [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

/ ** * A: Входной массив * B: выходной массив * lo: нижняя граница * привет: верхняя граница * выкл: смещение * /алгоритм parallelMergesort (A, lo, hi, B, off) равен len: = привет - lo + 1 если len == 1, то B [off]: = A [lo] иначе пусть T [1..len] будет новым массивом середина: = ⌊ (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 должны быть включены только один раз из-за их параллельного выполнения, получив

${\textstyle 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)}$.

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

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

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

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

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

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

Представленный последовательный алгоритм возвращает индексы разбиений в каждой последовательности, например индексы в последовательностях , у которых глобальный ранг меньше и . ^[16]${\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], к: целое) является  для I = 1 до п дел (l_i, r_i) = (0, | S_i | -1) пока существует i: l_i <r_i do// выбираем опорный элемент в 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 // присвоение вектораеще l: = 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 to 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 . Здесь необходимо учитывать следующие аспекты: Иерархия памяти., когда данные не помещаются в кэш процессоров, или накладные расходы на обмен данными между процессорами, которые могут стать узким местом, когда к данным больше нельзя получить доступ через общую память.

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

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

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

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

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

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

Примечания [ править ]

Ссылки [ править ]

• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (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 . Проверено 4 апреля 2009 .. Также практичная сортировка на месте . Также [3]
• Кнут, Дональд (1998). «Раздел 5.2.4: Сортировка путем слияния». Сортировка и поиск . Искусство программирования . 3 (2-е изд.). Эддисон-Уэсли. С. 158–168. ISBN 0-201-89685-0.
• Кронрод, М.А. (1969). «Оптимальный алгоритм заказа без операционного поля». Советская математика - Доклады . 10 : 744.
• LaMarca, A .; Ladner, RE (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. «API массивов (Java SE 6)» . Проверено 19 ноября 2007 .
• Oracle Corp. «Массивы (Java SE 10 и JDK 10)» . Проверено 23 июля 2018 .

Внешние ссылки [ править ]

В реализации алгоритма Викибука есть страница по теме: Сортировка слиянием

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