Проанализируем эффективность алгоритма для p процессоров и N.

Временные затраты на ускорение алгоритма:

Каждую итерацию массив делится случайно. На первой итерации при делении на 2 части с меньшими и большими элеменами с разделяющим ведущем пусть длина меньшей части n1. Алгоритм отправляет её на другой процессор сортироваться параллельно, а так как она короче, то и досортируется быстрее, значит время её сортировки не учитывается. Длина большей части N-n1, с этой частью мы проделываем точно такую же итерацию с разделителем n2. И так далее до момента, когда число свободных процессоров закончится, то есть до разделителя nk. Где p=2^k.

T1=[N+(N-n1)+(N-n1-n2)+...+(N-n1-...-nk)]*t, где t - время перестановки.

Временные затраты на работу алгоритма при максимальном ускорении:

После достижения максимального ускорения алгоритм будет работать в режиме стандартной быстрой сортировки. Последняя бОльшая, и поэтому учитываемая, часть будет иметь длину (N-n1-...-nk).

T2=[(N-n1-...-nk)log₂(N-n1-...-nk)]*t, где t - время перестановки.

Временные затраты на передачу частей массива процессам:

T3=(α+w/β)(log₂(p))^2 + (α+w(N/2p)/β)(log₂(p)), где α - латентность, β - пропускная способность сети, а w – размер элемента набора в байтах.

Общие временные затраты параллельного алгоритма:

T=T1+T2+T3 *В качестве n берется среднее число, которым может быть разбиение. То есть (из теории вероятности) - 3/4.