Изменения

===Алгоритм со Сортировка с однопоточным слиянием за <math>\Omega(n)</math>===

В данном алгоритме оператор '''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>Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма: <math>T(n) = T(n / 2) + \OmegaTheta(n) = \OmegaTheta(n)</math>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.<br>

Данный алгоритм будет иметь асимптотику: <math>\OmegaTheta((n / maxThreads) * \log((n / maxThreads)))</math>.

===Алгоритм с многопоточным слияниемМногопоточное слияние===Как видно из оценки первого алгоритма, слияние выполняется слишком долго при том, что существует возможность его ускорить. Рассмотрим алгоритм рекурсивного слияния массивов <math>T[left1 left_{1} \dots right1right_{1}]</math> и <math>T[left2 left_{2} \dots right2right_{2}]</math> в массив <math>A[left3 left_{3} \dots right3right_{3}]</math>:# Убедимся, что размер <math>T[left1 left_{1} \dots right1right_{1}]</math> больше либо равен размеру <math>T[left2 left_{2} \dots right2right_{2}]</math># Найдем Вычислим <math>x = T[mid1mid_{1}]</math> - середину первого массива (<math>x</math> также является и медианой этого массива)# При помощи бинарного поиска найдем <math>mid2mid_{2}</math> такое, что <math>\forall y \in T[left2 left_{2} \dots mid2 mid_{2} - 1]: y < x</math># <math>mid3 mid_{3} = left3 left_{3} + (mid1 mid_{1} - left1left_{1}) + (mid2 mid_{2} - left2left_{2})</math># <math>A[mid3mid_{3}] = x</math># Сольем <math>T[right1 right_{1} \dots mid1 mid_{1} - 1]</math> и <math>T[rigth2 right_{2} \dots mid2mid_{2}]</math> в <math>A[right3 right_{3} \dots mid3 mid_{3} - 1]</math># Сольем <math>T[mid1 mid_{1} + 1 \dots right1right_{1}]</math> и <math>T[mid2 mid_{2} \dots right2right_{2}]</math> в <math>A[mid3 mid_{3} + 1 \dots right3right_{3}]</math>Приведем Рассмотрим псевдокод данного алгоритма:

// слияние <math>T[left1 left_{1} \dots right1right_{1}]</math> и <math>T[left2 left_{2} \dots right2right_{2}]</math> в <math>A[left3 left_{3} \dots right1 right_{1} - left1 left_{1} + right2 right_{2} - left2left_{2}]</math> mergeMT(T, left1<math>left_{1}</math>, right1<math>right_{1}</math>, left2<math>left_{2}</math>, right2<math>right_{2}</math>, A, left3<math>left_{3}</math>): n1 <math>n_{1}</math> = right1 <math>right_{1}</math> - left1 <math>left_{1}</math> + 1 n2 <math>n_{2}</math> = right2 <math>right_{2}</math> - left2 <math>left_{2}</math> + 1 if n1 < n2math>n_{1}</math> < <math>n_{2}</math>: swap(left1<math>left_{1}</math>, left2<math>left_{2}</math>) swap(right1<math>right_{1}</math>, right2<math>right_{2}</math>) swap(n1<math>n_{1}</math>, n2<math>n_{2}</math>)

if n1 <math>n_{1}</math> == 0:

mid1 <math>mid_{1}</math> = (left1 <math>left_{1}</math> + right1<math>right_{1}</math>) / 2 mid2 <math>mid_{2}</math> = binarySearch(T[mid1<math>mid_{1}]</math>, T, left2<math>left_{2}</math>, right2<math>right_{2}</math>) mid3 <math>mid_{3}</math> = left3 <math>left_{3}</math> + (mid1 <math>mid_{1}</math> - left1<math>left_{1}</math>) + (mid2 <math>mid_{2}</math> - left2<math>left_{2}</math>) A[mid3<math>mid_{3}</math>] = T[mid1<math>mid_{1}</math>] '''spawn''' mergeMT(T, left1<math>left_{1}</math>, mid1 <math>mid_{1}</math> - 1, left2<math>left_{2}</math>, mid2 <math>mid_{2}</math> - 1, A, left3<math>left_{3}</math>) mergeMT(T, mid1 <math>mid_{1}</math> + 1, right1<math>right_{1}</math>, mid2<math>mid_{2}</math>, right2<math>right_{2}</math>, A, mid3 <math>mid_{3}</math> + 1)