Tom Franken: Parallel Sorting Under Assumptions.


Event Details


The talk will explore parallel sorting with the following assumptions on the parallel processors:

  • The processors can only save a constant amount of parameters.
  • The processors need references to access other processors.

Notably, I’ll take a look at sorting networks and the AKS network and at Richard Cole’s Parallel Merge Sort algorithm, to see whether they can be adapted to work with O(n) processors in O(log n) time under the two assumptions.