java - 实现合并排序算法的工作线程

Question

我有一个合并排序的单线程版本 http://pastebin.com/2uMGjTxr

它创建一个数组，用随机数填充它并在其上调用执行归并排序的排序方法:

private static int[] sort(int[] array) {
    //TODO: use multiple threads to speed up the sorting

    return mergeSort(array, 0, array.length);
}

现在我想使用 java 中的多线程技术来提高性能。代码来 self 的导师，他说我必须在排序方法中添加一些东西，但这实际上让我感到困惑。

归并排序是一种分而治之的算法:

• 如果列表的长度为 0 或 1，则它已经排序。否则:
• 将未排序的列表分成两个大约一半大小的子列表。
• 通过重新应用合并排序对每个子列表进行递归排序。
• 将两个子列表合并回一个排序列表。

所以我实际上会为每个子列表启动一个线程。你怎么认为？如何根据给定的实现并行化合并排序？有人知道我为什么要编辑排序方法吗？

Answer 1

这是使用 ForkJoin Framework 的一个很好的练习设置为在 Java 7.0 中发布。这正是您要寻找的。您只需将(fork)递归合并任务提交到池中，并在完成时加入结果。

您可以下载 JSR 166 Binary .更多信息this是一篇不错的文章

编辑以解决您的评论:

如果你想自己实现它，你不会希望每个子列表都有一个新的线程。您可以想象给定数组将有许多分区需要排序，因此每个分区的线程会变得很大(假设数组足够大)。相反，您需要为每个您实际要进行合并工作的分区数组创建一个线程。 ForkJoin 为您做这件事，使用 FJ 池的好处之一是它将重用线程而不是为子进程合并创建新线程。