Multithreaded Divide and Conquer

During my time as CS student the implementation of a divide and conquer algorithm was pretty straight forward:

  1. Take an amount of objects (usually an array and usually of type integer)
  2. Select a pivot element that splits the amount in half
  3. Do some computation with the two halves. E.g. for sorting make sure that all elements greater than the pivot are contained in one half and the rest in the other.
  4. Call the algorithm recursively for the two halves.

Since then one thing changed that make it possible to speed the computation up: Multiple CPU cores that allow for multi-threading.
„Multithreaded Divide and Conquer“ weiterlesen