Multithreaded Merge Sorting

Question

Can someone please give me a link or provide me Java code for multithreaded merging?

Preferred that the performer uses!

Thank you very much!

Answer 1

Here is my version of MergeSort using 2 threads, it can be easily expanded to n threads (just divide the original array into n subarrays). For 10 million numbers, it is faster than its single-threaded counterpart by about 25%.

import java.util.Random; public class MergeSortThreaded { public static void finalMerge(int[] a, int[] b) { int[] result = new int[a.length + b.length]; int i=0; int j=0; int r=0; while (i < a.length && j < b.length) { if (a[i] <= b[j]) { result[r]=a[i]; i++; r++; } else { result[r]=b[j]; j++; r++; } if (i==a.length) { while (j<b.length) { result[r]=b[j]; r++; j++; } } if (j==b.length) { while (i<a.length) { result[r]=a[i]; r++; i++; } } } } public static void main(String[] args) throws InterruptedException { Random rand = new Random(); int[] original = new int[10000000]; for (int i=0; i<original.length; i++) { original[i] = rand.nextInt(1000); } long startTime = System.currentTimeMillis(); int[] subArr1 = new int[original.length/2]; int[] subArr2 = new int[original.length - original.length/2]; System.arraycopy(original, 0, subArr1, 0, original.length/2); System.arraycopy(original, original.length/2, subArr2, 0, original.length - original.length/2); Worker runner1 = new Worker(subArr1); Worker runner2 = new Worker(subArr2); runner1.start(); runner2.start(); runner1.join(); runner2.join(); finalMerge (runner1.getInternal(), runner2.getInternal()); long stopTime = System.currentTimeMillis(); long elapsedTime = stopTime - startTime; System.out.println("2-thread MergeSort takes: " + (float)elapsedTime/1000 + " seconds"); } } class Worker extends Thread { private int[] internal; public int[] getInternal() { return internal; } public void mergeSort(int[] array) { if (array.length > 1) { int[] left = leftHalf(array); int[] right = rightHalf(array); mergeSort(left); mergeSort(right); merge(array, left, right); } } public int[] leftHalf(int[] array) { int size1 = array.length / 2; int[] left = new int[size1]; for (int i = 0; i < size1; i++) { left[i] = array[i]; } return left; } public int[] rightHalf(int[] array) { int size1 = array.length / 2; int size2 = array.length - size1; int[] right = new int[size2]; for (int i = 0; i < size2; i++) { right[i] = array[i + size1]; } return right; } public void merge(int[] result, int[] left, int[] right) { int i1 = 0; int i2 = 0; for (int i = 0; i < result.length; i++) { if (i2 >= right.length || (i1 < left.length && left[i1] <= right[i2])) { result[i] = left[i1]; i1++; } else { result[i] = right[i2]; i2++; } } } Worker(int[] arr) { internal = arr; } public void run() { mergeSort(internal); } } 

Answer 2

I would suggest that multi-threaded merge is very similar to a regular merge, however, when mergesort is recursively called, each half of the list is set up with its own algorithm to call each merge in a new thread. Then you can wait for both threads to finish, and then merge the two lists together and return. Plain!

In your question, you will say that you want to use Executor - I would suggest that the java.util.concurrent package will be used for it, especially the Future interface.

Resources

• Mergesort
• Java Themes
• Concurrent programming with J2SE 5.0

Answer 3

I tried using the join method. It basically spawns threads for each additional problem and waits for the spawned thread to finish using the connection.

Let me know your comments.

  package com.kayan.dsAlgo; public class MergeSorter implements Runnable{ private int[] arr; private int Size; private int left; private int right; private int[] resultArr ; public MergeSorter(int[] arr, int i, int j) { this.arr = arr; this.Size = arr.length; //this.resultArr = new int[j-i+1]; this.left = i; this.right = j; } @Override public void run() { System.out.println("Starting new thread left :"+this.left+" right "+this.right); sort(); } public static void main(String[] args) { int arr[] ={3,6,4,2,1,10} ; MergeSorter mr = new MergeSorter(arr,0,arr.length-1); Thread t = new Thread(mr); t.start(); //mr.run(); try { t.join(); } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace(); } for (int i :mr.resultArr) System.out.print(i+" "); //int res[]= mr.sort(0,arr.length-1); } private void sort() { if(left==right && left >=0 ) { this.resultArr = new int[]{arr[left]}; return; } if(left>right) return; int rightLimit = this.left+(right-left)/2; //int leftArr[] = sort( left,rightLimit ); MergeSorter mleft = new MergeSorter(arr,left,rightLimit); Thread t1 = new Thread(mleft); t1.start(); int leftlimit = 1 + rightLimit; //int rightArr[] = sort(leftlimit , right); MergeSorter mright= new MergeSorter(arr,leftlimit,right); Thread t2 = new Thread(mright); t2.start(); try { t1.join(); t2.join(); } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace(); } merge(mleft.resultArr,mright.resultArr); } private int[] merge(int[] left, int[] right) { resultArr = new int[left.length+right.length]; int r=0; int i=0; int j=0; while(i<left.length && j <right.length ) { if( i<left.length && j<right.length && left[i] < right[j] ) resultArr[r++] = left[i++]; else if( j<right.length && i<left.length && right[j] < left[i]) resultArr[r++] = right[j++]; } while(i<left.length) { resultArr[r++] = left[i++]; } while(j<right.length) { resultArr[r++] = right[j++]; } //System.out.println("resultArr "+resultArr); return resultArr; } } 

Answer 4

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 using the beta here: http://gee.cs.oswego.edu/dl/concurrency-interest/