Чтобы оценить время работы алгоритма, составим рекуррентное соотношение. Пусть T(n) - время сортировки массива длины n, тогда для сортировки слиянием справедливо T(n) = 2T(n/2)+O(n) (O(n) - это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:

Осталось оценить k. Мы знаем, что 2^k = n, а значит k = log₂n. Уравнение примет вид:

Так как T(1) - константа, то T(n) = O(n) + log₂nO(n)=O(n∙log₂n).

Для анализа будем использовать следующие показатели:

·         T₁ - время решения задачи на одном процессоре.

·         T_p - время решения задачи на p процессорах.

·         S - ускорение. Ускорение определяется из отношения: S=T₁/T_p

 Таким образом, оценка сложности последовательного алгоритма

.

 Для оценки работы на p потоках оценим трудоемкость слияния отсортированных массивов, которые передаются по кольцу:

 Тогда работе на p потоках мы получим следующую оценку:

Исходя из полученных результатов можно дать оценку полученному ускорению:

.

Так же, для оценки сложности, необходимо учитывать время, затраченное на передачу данных. Данная оценка проводится с использованием модели Хокни: T = alfa+w/beta; где alfa и beta - латентность и пропускная способность среды передачи соответственно, w - объём памяти, требуемый для хранения элемента данных. Для приведенной программы формула трудоемкости представлена ниже. В ней учитывается начальная рассылка частей массива процессом с номером 0, а так же передача отсортированной части массива следующему по номеру процессу: