Определим сложность последовательного алгоритма. Если количество элементов массива n, тогда количество сравнений при слиянии n . Количество уровней рекурсии log₂n, тогда время выполнения последовательной задачи:

T₁ = t*nlog₂n

Определим сложность параллельного алгоритма. Каждый процесс производит сортировку слиянием блока размером n/p, где n - количество элементов массива, p - количество процессов. Получаем оценку:

t₁ = (n/p)*log₂(n/p)

Отсортированные блоки сливаются на нулевом процессе, количество сравнений при каждом слиянии 2*n/p, всего присходит p итерраций слияния, следовательно

t₂ = p*(2n/p)=2n

Общее время всех выполняемых в ходе сортировки операций передачи блоков можно оценить при помощи соотношения вида

где a - латентность, b - пропускная способность сети передачи данных, w - размер элемента упорядочиваемых данных в байтах.

Время выполнения параллельного алгоритма сортировки слиянием определяется суммой

T_p = T_p(comm)+ t₁ + t₂,

T_p = p(a+w(n/p)/b)+t((n/p)*log₂(n/p) + 2n)

Соответственно ускорение равно:

S_p = tnlog₂n  /  [p(a+w(n/p)/b)+t((n/p)*log₂(n/p) + 2n)]   

Ускорение:

E_p = tnlog₂n  /  p[p(a+w(n/p)/b)+t((n/p)*log₂(n/p) + 2n)]