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

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

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

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

Алгоритм

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

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, длина(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  [  я  ]; 
  } 

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

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

функция  merge_sort(  список  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. ^я или ноль . node — это ссылка или указатель на узел. Функция merge() аналогична той, что показана в примере слияния списков сверху вниз: она объединяет два уже отсортированных списка и обрабатывает пустые списки. В этом случае merge() будет использовать node в качестве входных параметров и возвращаемого значения.

функция  merge_sort (  узла  )  заголовок 
      // возвращаем, если список пустой 
      если  head = ноль  , то 
         вернуть  ноль 
      var   массив узлов  [32];   изначально все ноль 
      var   узла  результат 
      вар   узел  следующий 
      вар   int  я 
      результат := голова 
      // объединяем узлы в массив 
      пока  результат ≠ ноль,  делайте 
          следующий: = 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 шагов, предпринятых для объединения полученных двух списков). Замкнутая форма следует из основной теоремы для повторений по принципу «разделяй и властвуй» .

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

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

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

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

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

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

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

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

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

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

Вместо объединения двух блоков за раз, слияние в пинг-понге объединяет четыре блока за раз. Четыре отсортированных блока одновременно объединяются во вспомогательное пространство в два отсортированных блока, затем два отсортированных блока объединяются обратно в основную память. При этом операция копирования исключается и общее количество ходов уменьшается вдвое. Ранняя общедоступная реализация слияния «четыре одновременно» была реализована WikiSort в 2014 году. Позже в том же году этот метод был описан как оптимизация для терпеливой сортировки и назван слиянием «пинг-понг». Quadsort реализовала этот метод в 2020 году и назвала его четырехкратным слиянием.

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

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

• Кронрод (1969) предложил альтернативную версию сортировки слиянием, в которой используется постоянное дополнительное пространство.
• Катаджайнен и др. представить алгоритм, который требует постоянного объема рабочей памяти: достаточно места для хранения одного элемента входного массива и дополнительного места для хранения указателей O (1) во входном массиве. Они достигают времени O ( n log n ) с небольшими константами, но их алгоритм нестабилен.
• Было предпринято несколько попыток создать алгоритм слияния на месте , который можно объединить со стандартной сортировкой слиянием (сверху вниз или снизу вверх) для создания сортировки слиянием на месте. В этом случае понятие «на месте» можно ослабить до значения «занимать логарифмическое пространство стека», поскольку стандартная сортировка слиянием требует такого количества места для собственного использования стека. Это было показано Geffert et al. что стабильное слияние на месте возможно за время O ( n log n ) с использованием постоянного объема рабочего пространства, но их алгоритм сложен и имеет высокие постоянные коэффициенты: слияние массивов длины n и m может занять 5 n + 12 m. + o ( м ) движется. Этот высокий постоянный коэффициент и сложный алгоритм на месте стали проще и понятнее. Бин-Чао Хуан и Майкл А. Лэнгстон представил простой алгоритм линейного времени, практическое слияние на месте для объединения отсортированного списка с использованием фиксированного объема дополнительного пространства. Они оба использовали работы Кронрода и других. Он сливается в линейном времени и постоянном дополнительном пространстве. Алгоритм в среднем занимает немного больше времени, чем стандартные алгоритмы сортировки слиянием, позволяя использовать O(n) временных дополнительных ячеек памяти, менее чем в два раза. Хотя на практике алгоритм намного быстрее, но он нестабильен и для некоторых списков. Но используя аналогичные концепции, они смогли решить эту проблему. Другие встроенные алгоритмы включают SymMerge, который в общей сложности занимает O (( n + m ) log ( n + m )) времени и является стабильным. Подключение такого алгоритма к сортировке слиянием увеличивает его сложность до нелинейной , но все же квазилинейной , O ( n (log n ) ² ) .
• Многие приложения внешней сортировки используют форму сортировки слиянием, при которой входные данные разбиваются на большее количество подсписков, в идеале на такое количество, для которого их объединение по-прежнему позволяет помещать обрабатываемый в данный момент набор страниц в основную память.
• Современный стабильный вариант линейного слияния и слияния на месте — это сортировка слиянием блоков , при которой создается раздел уникальных значений для использования в качестве пространства подкачки.
• Затраты на пространство можно уменьшить до sqrt( n ), используя двоичный поиск и ротацию. Этот метод используется библиотекой C++ STL и квадросортировкой.
• Альтернативой сокращению копирования в несколько списков является связывание нового поля информации с каждым ключом (элементы в 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. Повторяйте, пока не получите один список, содержащий все отсортированные данные — в журнале _{проходит 2} ( n ).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

/** 
   * 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 должны быть включены только один раз из-за их параллельного выполнения, получая

$$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).$$

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

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

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

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

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

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

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

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

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

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

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

Выбор нескольких последовательностей

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

Представленный последовательный алгоритм возвращает индексы разбиений в каждой последовательности, например индексы $l_{i}$ в последовательностях $S_{i}$ такой, что $S_{i}[l_{i}]$ имеет глобальный ранг меньше, чем $k$ и $\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], равномерно выбираем случайный j 
	  v := PickPivot(S, l, r) 
	  для  i = 1  до  p  сделать  
	      m_i =binarySearch(v, S_i[l_i, r_i]) // последовательно 
	  если  m_1 + ... + m_p >= k  , то  // m_1+ ... + m_p — глобальный ранг v 
	      r := m // присвоение вектора 
	  еще 
	      л := м  
	
      вернуть  л 
 

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

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

Псевдокод

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

/** 
   * d: Несортированный массив элементов 
   * n: количество элементов 
   * p: количество процессоров 
   * вернуть отсортированный массив 
   */ 
  Алгоритм  ParallelMultiwayMergesort(d: Array, n: int, p: int  ) 
      o :=  new  Array[0, n] // выходной массив 
      от  i = 1  до  p  делать параллельно  // каждый процессор параллельно 
          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] := кВтayMerge(s_1,i, ..., s_p,i) // объединяем и присваиваем выходному массиву 
	
      вернуться  о 
 

Анализ

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

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

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

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

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

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

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

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

Timsort , настроенный гибрид сортировки слиянием и сортировки вставкой, используется на различных программных платформах и языках, включая платформы Java и Android. и ранее использовался Python с версии 2.3 по версию 3.10.

Ссылки

• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (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. Сортировка слиянием , Пэт Морин.