# Parallel merge sort using hypercube connection template

I've been reading about hypercube connection template for parallel algorithms. The general scheme is explained in Designing and Building Parallel Programs by Ian Foster and it's pretty clear.

What I don't understand is how it's applied on the merge sort in §11.4 The point I'm most interested is the parallel_merge function in the pseudocode, i.e. parallel merge algorithm.

The point I'm most interested is the parallel_merge function in the pseudocode, i.e. parallel merge algorithm.

procedure parallel_mergesort(myid, d, data, newdata)
begin
data = sequential_mergesort(data)
for dim = 1 to d
data = parallel_merge(myid, dim, data)
endfor
newdata = data
end


Please, explain to me step by step, assuming we have an array of twelve elements $(3,1,5,7,4,2,8,9,4,2,7,5)$ and we've broken this data to four processors like this:

$\qquad ((3,1,5),(7,4,2),(8,9,4),(2,7,5))$.

What data will have each process after each iteration? I understand why we use the hybercube template in this algorithm, but why do we have exactly $i$ compare-exchanges at the $i$-th level? I mean, when $i=1$, we compare-exchange data from processes $1-2, 3-4, .. P-1, P$. That's not $1$, that's $P/2$? Do I misunderstand something?

The $i$-th parallel merge takes two sequences, each distributed over $2^{i-1}$ tasks, and generates a sorted sequence distributed over $2^i$ tasks.
For $i=1$, that reads
That is, every node performs one compare-merge. Similarly, for higher $i$, each node performs $i$ such operations.
They use it to derive "per-processor communication cost" $T_{comm}$ which clarifies that they do indeed count processor-wise in the prequel. That makes sense, too: communication happens in parallel, so in order to derive bounds on overall runtime you can bound every (abstract) step from above with the longest processing time found among all processors in that step.