Изменения

Благодаря тому, что сортировка слиянием построена на принципе "Разделяй и властвуй", выполнение данного алгоритма можно весьма эффективно распараллелить. Теоретически можно достичь много лучшей асимптотики, однако на практике из-за огранечений по количеству потоков, которые могут выполняться независимо друг от друга, вычислительная сложность уменьшается на константу.

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