Java 多线程快速排序或合并排序

Question

如何为Java实现并发的quicksort或mergesort算法？

我们在16（虚拟）核的Mac上遇到问题，其中只有一个核（！）使用默认的Java排序算法工作，而且很好的机器没有得到充分利用是不好的。因此，我们编写了自己的代码（我编写了代码），并且确实取得了不错的提速（我编写了多线程快速排序，由于其分区特性，它可以很好地并行化，但我也可以编写合并排序）……但是我的实现只能扩展最多4个线程，这是专有代码，我宁愿使用一个来自知名来源的线程，也不要使用重新发明的轮子。

我在网上找到的唯一一个例子是如何不使用Java编写多线程快速排序的示例，它使用以下命令进行忙循环（这确实很糟糕）：

while (helpRequested) { }

http://broadcast.oreilly.com/2009/06/may-column-multithreaded-algor.html

因此，除了无缘无故丢失一个线程外，还要确保通过在while循环中进行忙循环来杀死perfs（这令人难以置信）。

因此，我的问题是：你是否知道有信誉良好的Java中正确的多线程quicksort或mergesort实现？

我强调的事实是，我知道复杂度保持为O（n log n），但是我仍然非常高兴看到所有这些内核开始工作而不是空转。请注意，对于其他任务，在相同的16个虚拟内核Mac上，通过并行处理代码，我看到了高达x7的加速（而且我绝不是并发专家）。

因此，即使复杂度保持为O（n log n），我也非常感谢x7或x8甚至x16的加速。

Answer 1

尝试使用Doug Lea的fork / join框架：

public class MergeSort extends RecursiveAction {
    final int[] numbers;
    final int startPos, endPos;
    final int[] result;

    private void merge(MergeSort left, MergeSort right) {
        int i=0, leftPos=0, rightPos=0, leftSize = left.size(), rightSize = right.size();
        while (leftPos < leftSize && rightPos < rightSize)
            result[i++] = (left.result[leftPos] <= right.result[rightPos])
                ? left.result[leftPos++]
                : right.result[rightPos++];
        while (leftPos < leftSize)
            result[i++] = left.result[leftPos++];
        while (rightPos < rightSize)
        result[i++] = right.result[rightPos++];
    }

    public int size() {
        return endPos-startPos;
    }

    protected void compute() {
        if (size() < SEQUENTIAL_THRESHOLD) {
            System.arraycopy(numbers, startPos, result, 0, size());
            Arrays.sort(result, 0, size());
        } else {
            int midpoint = size() / 2;
            MergeSort left = new MergeSort(numbers, startPos, startPos+midpoint);
            MergeSort right = new MergeSort(numbers, startPos+midpoint, endPos);
            coInvoke(left, right);
            merge(left, right);
        }
    }
}