合并排序算法在多线程上较慢

Question

对于我的 class 我必须在多线程中实现合并排序算法并将其时间与单线程版本进行比较。我知道它应该更快，但我得到的时间却不是这样。对于大小为 1000000+ 的数组，多线程版本变得更快，即使那样也没有显着差异。我提供我正在使用的代码。难道我做错了什么？我对多线程没有太多经验

public Sorter() {  


public void mergeSortMultiThread(int[] array, int start, int end){
    if(start < end){
        // Find the middle point
        int m = (start+end)/2;
        Thread t1 = new Thread(() -> mergeSortSequence(array, start, m));
        t1.start();
        mergeSortSequence(array , m+1, end);
        try {
            t1.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        // Merge the sorted halves
        merge(array, start, m, end);
    }
}

public void mergeSortSnngleThread(int[] array, int start, int end){
    if(start < end){
        // Find the middle point
        int m = (start+end)/2;

        // Sort first and second halves
        mergeSortSequence(array, start, m);
        mergeSortSequence(array , m+1, end);

        // Merge the sorted halves
        merge(array, start, m, end);
    }
}

private void merge(int arr[], int l, int m, int r)
{
    // Find sizes of two subarrays to be merged
    int n1 = m - l + 1;
    int n2 = r - m;

    /* Create temp arrays */
    int L[] = new int [n1];
    int R[] = new int [n2];

    /*Copy data to temp arrays*/
    for (int i=0; i<n1; ++i)
        L[i] = arr[l + i];
    for (int j=0; j<n2; ++j)
        R[j] = arr[m + 1+ j];


    /* Merge the temp arrays */

    // Initial indexes of first and second subarrays
    int i = 0, j = 0;

    // Initial index of merged subarry array
    int k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    /* Copy remaining elements of L[] if any */
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* Copy remaining elements of R[] if any */
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

}

Answer 1

您犯了两个基本错误：

首先是线程的创建，创建线程是比较耗时的，为此最好使用线程池或者标准的javaapi: ExecutorService.
另一个基本错误是你使用的线程数，当你进行递归调用时，你会不断增加处理器中的线程数，你必须意识到从一定数量开始在线程中，工作并没有真正并行化，因为处理器没有足够的核心来同时执行这项工作，但是多线程管理引入的过载确实会影响性能。

这个答案可以帮助您了解如何利用多线程：Multithreaded merge sort, adding additional threads

Answer 2

不是动态创建线程，而是将数组拆分为 k 个块，然后使用 k 个线程对 k 个块中的每个块进行排序，然后在每个线程完成其任务时合并排序后的块。合并也可以是多线程的。假设您使用 4 个块，并使用 4 个线程。每个线程 0、1、2、3 对其块进行排序。线程 1 和 3 在对它们的块进行排序后终止。线程 2 对它的块进行排序后，它等待线程 3 完成，然后合并块 2 和 3。线程 0 对它的块进行排序后，它等待线程 1 完成，然后合并块 0 和 1，然后等待线程 2 完成完成，然后将合并的 0+1 块与合并的 2+3 块合并。

合并排序算法在多线程上较慢

Merge sort algorithm is slower on multi thread

java

sorting

mergesort

multithreading