Java 多线程归并排序

Multithreaded Merge Sort

提问by Jacob Williams

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

有人可以给我一个链接或向我提供多线程合并排序的java代码吗？

Preferable one that uses an executor!

最好是使用 executor 的！

Thank you very much!

非常感谢！

回答by Noel M

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.concurrentpackage would be of use for this, particularly the Futureinterface.

您在问题中说您想使用Executor- 我建议该java.util.concurrent包对此有用，尤其是Future接口。

Resources:

资源：

• Mergesort
• Java Threads
• Concurrent Programming with J2SE 5.0

• 归并排序
• Java 线程
• 使用 J2SE 5.0 进行并发编程

回答by Enno Shioji

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

下面是一个使用 Java7 ForkJoin 框架的例子：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/

您可以通过在此处使用测试版在 Java6 中使用此框架：http: //gee.cs.oswego.edu/dl/concurrency-interest/

回答by PoweredByRice

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

这是我使用 2 个线程的 MergeSort 版本，它可以轻松扩展到 n 个线程（只需将原始数组拆分为 n 个子数组）。对于 1000 万个数字，它比单线程快约 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);
    }
}

回答by Kalyan Chakravarthi

I tried just using join method. It basically spawns the threads for each sub problem and waits for the spawned thread to complete using join.

我试过只使用 join 方法。它基本上为每个子问题生成线程并等待生成的线程使用 join 完成。

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;
}



}