Обсуждение участника:AKhimulya

Многопоточная сортировка слиянием

Благодаря тому, что сортировка слиянием построена на принципе "Разделяй и властвуй", выполнение данного алгоритма можно весьма эффективно распараллелить. Теоретически можно достичь много лучшей асимптотики, однако на практике из-за огранечений по количеству потоков, которые могут выполняться независимо друг от друга, вычислительная сложность уменьшается на константу.

Алгоритм со слиянием за [math]\Omega(n)[/math]

Внесем в алгоритм сортировки слиянием следующую модификацию: будем сортировать левую и правую части массива параллельно.

   mergeSortMT(array, left, right):
       mid = (left + right) / 2
   
       spawn mergeSortMT(array, left, mid)
       mergeSortMT(array, mid + 1, right)
       sync
   
       merge(array, left, mid, right)

В данном алгоритме оператор spawn запускает новый поток, а оператор sync ожидает завершения этого потока. Функция merge аналогична функции merge из раздела слияние двух массивов. Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма: [math]T(n) = T(n / 2) + \Omega(n) = \Omega(n)[/math]. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга. На практике на однопроцессорных компьютерах имеет смысл запускать алгоритм, ограничив количество допустимое количество потоков. Изменим код в соответствии с этими требованиями:

   mergeSortMTBounded(array, left, right):
       mid = (left + right) / 2
   
       if threadCount [math]\lt [/math] maxThreads:
           threadCount++
           spawn mergeSortMTBounded(array, left, mid)
       else:
           mergeSortMTBounded(array, left, mid)
       mergeSortMTBounded(array, mid + 1, right)
       if threadCount [math]\leqslant[/math] maxThreads:
           sync
           threadCount--
   
       merge(array, left, mid, right)

Где threadCount - глобальный счетчик, а maxThreads - ограничение по количеству потоков. Данный алгоритм будет иметь асимптотику: [math]\Omega((n / maxThreads) * \log((n / maxThreads)))[/math].

Алгоритм с многопоточным слиянием

Как видно из оценки первого алгоритма, слияние выполняется слишком долго при том, что существует возможность его ускорить. Рассмотрим алгоритм рекурсивного слияния массивов [math]T[left1 \dots right1][/math] и [math]T[left2 \dots right2][/math] в массив [math]A[left3 \dots right3][/math]:

1. Убедимся, что размер [math]T[left1 \dots right1][/math] больше либо равен размеру [math]T[left2 \dots right2][/math]
2. Найдем [math]x = T[mid1][/math] - середину первого массива ([math]x[/math] также является и медианой этого массива)
3. При помощи бинарного поиска найдем [math]mid2[/math] такое, что [math]\forall y \in T[left2 \dots mid2 - 1]: y \lt x[/math]
4. [math]mid3 = left3 + (mid1 - left1) + (mid2 - left2)[/math]
5. [math]A[mid3] = x[/math]
6. Сольем [math]T[right1 \dots mid1 - 1][/math] и [math]T[rigth2 \dots mid2][/math] в [math]A[right3 \dots mid3 - 1][/math]
7. Сольем [math]T[mid1 + 1 \dots right1][/math] и [math]T[mid2 \dots right2][/math] в [math]A[mid3 + 1 \dots right3][/math]

Приведем псевдокод данного алгоритма:

   // если [math]right \lt = left[/math] возвращает [math]left[/math]
   // если [math]x \lt = T[left][/math], возвращает [math]left[/math]
   // иначе возвращает наибольший индекс [math]i[/math] из отрезка [math][left; right][/math] такой, что [math]array[i - 1] \lt  x[/math]
   binarySearch(x, array, left, right)
   
   // слияние [math]T[left1 \dots right1][/math] и [math]T[left2 \dots right2][/math] в [math]A[left3 \dots right1 - left1 + right2 - left2][/math]
   mergeMT(T, left1, right1, left2, right2, A, left3):
   n1 = right1 - left1 + 1
   n2 = right2 - left2 + 1
   if n1 < n2:
       swap(left1, left2)
       swap(right1, right2)
       swap(n1, n2)
   
   if n1 == 0:
       return
   else
       mid1 = (left1 + right1) / 2
       mid2 = binarySearch(T[mid1], T, left2, right2)
       mid3 = left3 + (mid1 - left1) + (mid2 - left2)
       A[mid3] = T[mid1]
       spawn mergeMT(T, left1, mid1 - 1, left2, mid2 - 1, A, left3)
       mergeMT(T, mid1 + 1, right1, mid2, right2, A, mid3 + 1)
       sync