小编ave*_*bos的帖子

我做了两种快速排序的实现：顺序排序和并行排序。第二个是使用 ForkJoinPool 使用 4 个线程编写的（我在下面添加了实现）排序函数与 ArrayList 一起使用：

override fun sort(array: ArrayList<Int>): ArrayList<Int> { 
   ...
}

我在大小为 1e3-1e7 的数组上测试了它们，对于所有大小的并行实现比顺序执行快约 2.5 倍。但从size=1e8 开始，并行算法的运行速度比顺序算法慢约 2 倍。

class ParQuickSort(
    private val seqBlockSize:Int = 1000,
    nThreads: Int = 4
) : QuickSort {

    private val threadPool = ForkJoinPool(nThreads)

    override fun sort(array: IntArray): IntArray {
        threadPool.invoke(
            SortTask(array, 0, array.size - 1, seqBlockSize)
        )
        return array
    }

    fun shutdown() {
        threadPool.shutdownNow()
    }

    private class SortTask(
        val array: IntArray,
        val l: Int,
        val r: Int,
        val …