Изменения

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

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

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

mid = (left + right) / 2

Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма: <tex dpi="120">T(n) = T(\frac {n}{2}) + \Theta(n) = \Theta(n)</tex>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.<br>

Как видно из оценки первого алгоритма, слияние является его узким местом. Попытаемся распараллелить слияние, для чего рассмотрим алгоритм рекурсивного слияния массивов <tex dpi="120">T[left_{1} \dots right_{1}]</tex> и <tex dpi="120">T[left_{2} \dots right_{2}]</tex> в массив <tex dpi="120">A[left_{3} \dots right_{3}]</tex>:

[[Файл:MergeMT.png‎|430px|thumb|Слияние массивов]]

# Сольем <tex dpi="120">T[right_{1} \dots mid_{1} - 1]</tex> и <tex dpi="120">T[right_{2} \dots mid_{2}]</tex> в <tex dpi="120">A[right_{3} \dots mid_{3} - 1]</tex>

# Сольем <tex dpi="120">T[mid_{1} + 1 \dots right_{1}]</tex> и <tex dpi="120">T[mid_{2} \dots right_{2}]</tex> в <tex dpi="120">A[mid_{3} + 1 \dots right_{3}]</tex>

// если <tex dpi="120">right \leqslant left</tex> возвращает <tex dpi="120">left</tex>

// если <tex dpi="120">x \leqslant T[left]</tex>, возвращает <tex dpi="120">left</tex>

// слияние <tex dpi="120">T[left_{1} \dots right_{1}]</tex> и <tex dpi="120">T[left_{2} \dots right_{2}]</tex> в <tex dpi="120">A[left_{3} \dots right_{1} - left_{1} + right_{2} - left_{2}]</tex>

n<tex dpi="120">_{1}</tex> = right<tex dpi="120">_{1}</tex> - left<tex dpi="120">_{1}</tex> + 1

n<tex dpi="120">_{2}</tex> = right<tex dpi="120">_{2}</tex> - left<tex dpi="120">_{2}</tex> + 1

<tex dpi="135">\frac{n_{1}}{2} + n_{2} \leqslant \frac{n_{1}}{2} + \frac{n_{2}}{2} + \frac{n_{2}}{2} = \frac{(n_{1} + n_{2})}{2} + \frac{n_{2}}{2} \leqslant \frac{n}{2} + \frac{n}{4} = \frac{3}{4}n</tex>.<br>Асимптотика каждого вызова функции - <tex dpi="120">\Theta(\log n)</tex>, т.е. время, затрачиваемое на бинарный поиск. Так как рекурсивные вызовы функции выполняются параллельно, а потоки при оценке независимы, время их выполнения будет равно времени выполнения самого долгого вызова. В худшем случае это <tex dpi="120">T(\frac{3}{4}n)</tex>. Тогда получим оценку сверху<br><tex dpi="130">T_{\mathrm {merge}}(n) = T_{\mathrm {merge}}(\frac{3}{4}n) + \Theta(\log n) = \Theta(\log^2 n)</tex>

Приведем псевдокод алгоритма, использующего слияние из предыдущего раздела, сортирующего элементы <tex dpi="120">A[leftA \dots rightA]</tex> и помещающего отсортированный массив в <tex dpi="120">B[leftB \dots leftB + rightA - leftA]</tex>

n = r - p + 1

'''if''' n == 1

Оценим данный алгоритм сверху при условии, что возможен запуск неограниченного количества независимых потоков. Из предыдущих пунктов <tex dpi="130">T_{\mathrm {mergeSort}}(n) = T_{\mathrm {mergeSort}}(\frac{n}{2}) + T_{\mathrm {merge}}(n) = T_{\mathrm {mergeSort}}(\frac{n}{2}) + \Theta(\log^2 n) = \Theta(\log^3 n)</tex>.

Очевидно, что при отсутствии возможности запуска неограниченного количества независимых потоков, вычислительная сложность многопоточного алгоритма зависит от максимально возможного количества независимых потоков. Обозначим такое количество как <tex dpi="120">N_{ind}</tex>. Допустим, <tex dpi="120">n</tex> много больше <tex dpi="120">N_{ind}</tex>, что в общем случае верно для ПК и достаточно больших объемов данных. Оценим приведенные выше алгоритмы с учетом наложенных ограничений и допущений:<br>

::[[#.D0.A1.D0.BE.D1.80.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.BA.D0.B0_.D1.81_.D0.BE.D0.B4.D0.BD.D0.BE.D0.BF.D0.BE.D1.82.D0.BE.D1.87.D0.BD.D1.8B.D0.BC_.D1.81.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5.D0.BC|Сортировка с однопоточным слиянием]] будет иметь асимптотику <tex dpi="135">\Theta(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}} + n) = \Theta(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})</tex>:

::::<tex dpi="135">T_{\mathrm {mergeSort}}'(\frac{n}{N_{ind}}) = 2T_{\mathrm {mergeSort}}'(\frac{n}{2N_{ind}}) + \Theta(\frac{n}{N_{ind}})^{\log_{\frac{4}{3}}2} = \Theta(\frac{n}{N_{ind}})^{\log_{\frac{4}{3}}2}</tex>

Очевидно, что нижняя оценка алгоритма сортировки с многопоточным слиянием выше. Таким образом, при приведенных выше допущениях алгоритм сортировки с однопоточным слиянием эффективнее и его асимптотика составляет <tex dpi="120">\Theta(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})</tex>.