Algorithm for certain permutaion of array elements (parallel sorting by regular sampling) [C++] -

i implementing parallel sorting regular sampling algorithm described here. stuck in point @ need migrate sorted sublists proper places of sorted array. problem can stated in way: there 1 global array. array has been divided p subarrays.each of subarrays sorted. p-1 global pivot elements determined , each sub-array divided p sub-sub arrays (yellow, red, green). need move sub-sub-arrays sub-sub-arrays local index in thread (so ordered in such manner @ colors neighbouring , order left right remains).

actually serial algorithm do, have no clever idea how obtain proper permutation. following figure shows case p=3 threads. yellow color denotes sub-sub-array 0, red - 1, green - 2.

the sub-sub arrays may have different sizes.

ok seems don't have enough reputation comment on question, shall take route of posting answer.

so let me straigh. stuck on phase 3 of algo. right?

---

how this:

let's have p linkedlists of indexes. let each process communicate index ranges process i; indexes communicated, append indexes list of process i. when communications over, shall have indexes process in list of process i. node of list should data structre

 node {       index       valueofindex  } 

now populate list, copy value in list.

once through process. can recrate array process using list i.

????