Изменения

// если <math>right <= \leqslant left</math> возвращает <math>left</math> // если <math>x <= \leqslant T[left]</math>, возвращает <math>left</math>

mergeMT(T, left<math>left__{1}</math>, right<math>right__{1}</math>, left<math>left__{2}</math>, right<math>right__{2}</math>, A, left<math>left__{3}</math>): n<math>n__{1}</math> = right<math>right__{1}</math> - left<math>left__{1}</math> + 1 n<math>n__{2}</math> = right<math>right__{2}</math> - left<math>left__{2}</math> + 1 if n<math>n__{1}</math> < n<math>n__{2}</math>: swap(left<math>left__{1}</math>, left<math>left__{2}</math>) swap(right<math>right__{1}</math>, right<math>right__{2}</math>) swap(n<math>n__{1}</math>, n<math>n__{2}</math>)

if n<math>n__{1}</math> == 0:

mid<math>mid__{1}</math> = (left<math>left__{1}</math> + right<math>right__{1}</math>) / 2 mid<math>mid__{2}</math> = binarySearch(T[mid<math>mid__{1}]</math>], T, left<math>left__{2}</math>, right<math>right__{2}</math>) mid<math>mid__{3}</math> = left<math>left__{3}</math> + (mid<math>mid__{1}</math> - left<math>left__{1}</math>) + (mid<math>mid__{2}</math> - left<math>left__{2}</math>) A[mid<math>mid__{3}</math>] = T[mid<math>mid__{1}</math>] '''spawn''' mergeMT(T, left<math>left__{1}</math>, mid<math>mid__{1}</math> - 1, left<math>left__{2}</math>, mid<math>mid__{2}</math> - 1, A, left<math>left__{3}</math>) mergeMT(T, mid<math>mid__{1}</math> + 1, right<math>right__{1}</math>, mid<math>mid__{2}</math>, right<math>right__{2}</math>, A, mid<math>mid__{3}</math> + 1)

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

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

создадим новый массив T[1 <math>\dots </math> n]