Question 2

Give a complexity analysis for the lexicographic sorting on 3-D meshes. You should discuss seperately

• the case where the number $p$ of nodes equals the number $N$ of items to sort and
• the case where $N$ is larger than $p$ .

For $N >> p$ you should estimate the speed-up per processor $E(n,p)$ and comment on the scalability of this algorithm.