Does parallel mergesort run differently on mesh vs linear array of processors?

Question

I'm currently taking course on introduction to algorithm and I came across the parallel mergesort algorithm. My question is: Is there any differences in the algorithm plan if it runs on a 2d mesh instead of infinite linear proccessors ?

Thank you,

Answer 1

Please define the terms mesh and linear array of processors, and/or provide online references to such definitions.

---

There are different flavors of mergesort algorithms. One remarkable difference is:

• For merging two sorted halves of size N/2 arrays into a fully sorted N array, does it take exactly one stage (performing exactly N or O(N) comparisons), or does it take multiple stages, most commonly O(log(N)) as many stages (for a total number of O(N*log(N)) comparisons)?

---

• The single-threaded mergesort, the one typically taught in the introduction to programming classes, relies on scanning the two halves, "dequeuing" the smaller value of the two front values out of the two halves. This takes exactly N-1 comparisons. Because it is sequential, it takes O(N) time steps.

---

• The parallel mergesort, which is most likely a parallel bitonic mergesort, such as
  • http://en.wikipedia.org/wiki/Bitonic_sorter
  • http://pages.cs.wisc.edu/~tvrdik/17/html/Section17.html
  • Requires log(N) stages;
  • Inside each stage, O(N) comparisons are performed - one comparison per processing element - and all processing elements do this simultaneously.
  • Therefore, it requires O(log(N)) time, despite having performed vastly many more total number of comparisons of N*log(N)

---

There are other flavors of parallelized merge sort. I can't answer them unless you clarify what flavor of merge sort you're learning.