Java中的并发排序
我目前正在开发一个程序来同时对字符串进行排序。 我的程序接收一个文件，将文件的每一行读入一个数组，并将字符串数组拆分成较小的字符串数组。 然后程序为每个较小的arrays启动一个线程，并快速排序。 一旦每个线程完成对其数组的排序，主线程就会收集线程对象的所有结果。 然后，它应该将较小的，现在已排序的数组合并为一个大的排序数组。
我知道我的快速排序实现有效 – 使用一个线程程序对单词进行排序。 我需要的是一种将线程返回的数组嵌套在一起的算法。
任何帮助表示赞赏 – 提前谢谢。
从mergesort的最终merge过程开始 。 您读取每个m数组的第一个值（单个子数组的最小值），然后选择m个读取值的最小值（全局最小值），将其推入结果中并从包含的数组中删除它或增加相应的索引一个。 然后，迭代直到所有子数组都为空，或者所有索引都已到达相应数组的末尾。
注意：如果您有一个非常大的数据集（它实际上用于处理这种情况），这可能会减少内存使用量，但由于分割成本（如果您复制子arrays变为线性），可能会比原始Quicksort表现更差，并且multithreading开销。 考虑到应用于大型数组时，就地Mergesort更节省空间。 还要考虑编写Quicksort的用户可能花了很多时间来优化调用和分支执行。
这是基本的理论CS，但请注意，只能通过使用并行性来降低计算复杂度，只能获得线性加速度 。 最后，Quicksort恰好达到了比较排序算法的平均复杂度的下限：如果你试图超越Quicksort O(nlog(n))我O(nlog(n))你带来坏消息。
我认为使用合并排序是非常标准的。
我建议使用尽可能多的线程来开始使用CPU。
您可能会发现读取文件的时间比例很高，因此可以更快地对字符串进行排序。
例如，使用TreeSet的基数排序可能会更快，因为它将在您读取文件时进行排序。
您可以在此处使用合并程序。 该算法非常简单，请参阅维基百科上的合并排序 。 当两个数组合并时，Use可以使用简单的双向合并，当同时合并多个数组时，可以使用多路合并。
此外，请检查此工作： 具有最佳加速的并行化QuickSort和RadixSort 。
最后，还有可以并行的3向串快速排序 。
就像在其他post中提到的那样，算法的最后一步是mergesort。
但是，quicksort本身是一个递归算法，允许自然引入并发，使您的“合并步骤”过时，参见http://ricardozuasti.com/2012/java-concurrency-examples-forkjoin-framework/
在pivot元素处于最终位置后，您可以在两个分区上调用快速排序。 这可以同时完成。 由于这是递归的，因此它将跨越其他线程。