During my time as CS student the implementation of a divide and conquer algorithm was pretty straight forward:
- Take an amount of objects (usually an array and usually of type integer)
- Select a pivot element that splits the amount in half
- 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.
- 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