Изменения

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