146
правок
Изменения
Нет описания правки
В данном алгоритме оператор <tex>\mathrm {spawn}</tex> запускает новый поток, а оператор <tex>\mathrm {sync}</tex> ожидает завершения этого потока. Функция <tex>\mathrm {merge}</tex> аналогична одноименной функции из раздела [[Сортировка слиянием#Слияние двух массивов|слияние двух массивов]].<br>
Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма: <tex dpi="120150">T(n) = T(\frac {n}{2}) + \Theta(n) = \Theta(n)</tex>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.<br>
==Многопоточное слияние==
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: СортировкиСортировка]][[Категория: Многопоточные сортировки]]
