Изменения

В данном алгоритме оператор '''spawn''' запускает новый поток, а оператор '''sync''' ожидает завершения этого потока. Функция merge аналогична функции merge из раздела [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC[Сортировка слиянием#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5_.D0.B4.D0.B2.D1.83.D1.85_.D0.BC.D0.B0.D1.81.D1.81.D0.B8.D0.B2.D0.BE.D0.B2 |слияние двух массивов]].<br>Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма: <tex>T(n) = T(\frac{n / }{2}) + \Theta(n) = \Theta(n)</tex>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.<br>

# При помощи [[Целочисленный двоичный поиск|бинарного поиска ]] найдем <tex>mid_{2}</tex> такое, что <tex>\forall y \in T[left_{2} \dots mid_{2} - 1]: y < x</tex>

n<tex>_{1}</tex> = right<tex>_{1}</tex> - left<tex>_{1}</tex> + 1 n<tex>_{2}</tex> = right<tex>_{2}</tex> - left<tex>_{2}</tex> + 1 '''if''' n<tex>_{1}</tex> < n<tex>_{2}</tex>: swap(left<tex>_{1}</tex>, left<tex>_{2}</tex>) swap(right<tex>_{1}</tex>, right<tex>_{2}</tex>) swap(n<tex>_{1}</tex>, n<tex>_{2}</tex>)

'''if''' n<tex>_{1}</tex> == 0: '''return''' '''else''' mid<tex>_{1}</tex> = (left<tex>_{1}</tex> + right<tex>_{1}</tex>) / 2 mid<tex>_{2}</tex> = binarySearch(T[mid<tex>_{1}</tex>], T, left<tex>_{2}</tex>, right<tex>_{2}</tex>) mid<tex>_{3}</tex> = left<tex>_{3}</tex> + (mid<tex>_{1}</tex> - left<tex>_{1}</tex>) + (mid<tex>_{2}</tex> - left<tex>_{2}</tex>) A[mid<tex>_{3}</tex>] = T[mid<tex>_{1}</tex>] '''spawn''' mergeMT(T, left<tex>_{1}</tex>, mid<tex>_{1}</tex> - 1, left<tex>_{2}</tex>, mid<tex>_{2}</tex> - 1, A, left<tex>_{3}</tex>) mergeMT(T, mid<tex>_{1}</tex> + 1, right<tex>_{1}</tex>, mid<tex>_{2}</tex>, right<tex>_{2}</tex>, A, mid<tex>_{3}</tex> + 1) '''sync'''

Оба массива содержат <tex>n_{1} + n_{2} = n</tex> элементов. К моменту рекурсивных вызовов <tex>n_{2} \leqslant n_{1}</tex>, значит,<br><tex>n_{2} = 2 \cdot \frac{n_{2} / }{2 } \leqslant \frac{(n_{1} + n_{2}) / }{2 } = \frac{n / }{2}</tex>.<br> В худшем случае один из двух рекурсивных вызовов сольет <tex>\frac{n_{1} / }{2}</tex> элементов <tex>T[left_{1} \dots right_{1}]</tex> с <tex>n_{2}</tex> элементами <tex>T[left_{2} \dots right_{2}]</tex> и тогда количество элементов первых двух массивов в рекурсивном вызове будет равно<br><tex>\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 \cdot }{4}n / 4</tex>.<br>Асимптотика каждого вызова функции - <tex>\Theta(\log(n))</tex>, т.е. время, затрачиваемое на бинарный поиск. Так как рекурсивные вызовы функции выполняются параллельно, а потоки при оценке независимы, время их выполнения будет равно времени выполнения самого долгого вызова. В худшем случае это <tex>T(\frac{3 \cdot }{4}n / 4)</tex>. Тогда получим оценку сверху<br><tex>T_{merge}(n) = T_{merge}(\frac{3 \cdot }{4}n / 4) + \Theta(\log(n)) = \Theta(\log^2(n))</tex>

'''if''' n == 1:

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

Очевидно, что при отсутствии возможности запуска неограниченного количества независимых потоков, вычислительная сложность многопоточного алгоритма зависит от максимально возможного количества независимых потоков. Обозначим такое количество как <tex>N_{ind}</tex>. Допустим, <tex>n</tex> много больше <tex>N_{ind}</tex>, что в общем случае верно для ПК и достаточно больших объемов данных. на которых Оценим приведенные выше алгоритмы с учетом наложенных ограниченийи допущений:<br>::'''Сортировка с однопоточным слиянием''' будет иметь асимптотику <tex>\Theta(\frac{n/}{N_{ind}}\log(\frac{n/}{N_{ind}}) + n) = \Theta(\frac{n}{N_{ind}}\log(\frac{n}{N_{ind}}))</tex>:::::<tex>\Theta(\frac{n/}{N_{ind}}\log(\frac{n/}{N_{ind}}))</tex> операций нужно на последовательную сортировку массива длиной <tex>\frac{n/}{N_{ind}})</tex>.

::Соответветственно, асимптотика может быть как <tex>\Theta(n/N_{ind}\log(n/N_{ind}))</tex>, так и <tex>\Theta(n)</tex> в зависимости от <tex>N_{ind}</tex> и <tex>n</tex>::'''Многопоточное слияние''' будет работать за <tex>\Theta((\frac{n}{N_{ind}})^{(\log_{\frac{4}{3}}2)} + \log(n) \cdot min(N_{ind}, \log(n))=\Theta((\frac{n}{N_{ind}})^{(\log_{\frac{4}{3}}2)})</tex>: