Multithreaded Merge Sort

Question

Hi,

Can someone please give me a link or provide me with java code of a multithreaded merge sort?

Preferable one that uses an executor!

Thank you very much!

Answer 1

I'd suggest that a multithreaded mergesort is very similar to a regular mergesort, however, when recursively calling the mergesort each half of the list, set up your algorithm to call each merge in a new Thread. You can then wait until both threads are finished, and then merge the two lists together, and return. Simple!

You say in your question that you want to use an Executor - I'd suggest that the java.util.concurrent package would be of use for this, particularly the Future interface.

Resources:

• Mergesort
• Java Threads
• Concurrent Programming with J2SE 5.0

Answer 2

Here is an example that uses the Java7 ForkJoin framework: http://www.ibm.com/developerworks/java/library/j-jtp03048.html

You can use this framework in Java6 by using the beta version here: http://gee.cs.oswego.edu/dl/concurrency-interest/