多线程编程最好的排序算法是什么？

Question

我想对长度在1.000.000到100.000.000之间的整数数组进行排序。我想使用pthread库在一台2Mb缓存的core2duo计算机上运行这个程序。我想要最快的算法！

我已经写了一个使用mergesort算法的半并行排序代码。但是它还不够快！

          ___ sort___   
         /           \        
        /____ sort ___\     __ merge __
    ___/               \___/           \___ merge 
       \ ____ sort ____/   \__ merge __/    
        \             /      
         \___ sort __/      

Answer 1

我上大学已经有一段时间了，但我似乎记得PSRS算法很适合做这类事情。我相信google会公布大量的实现/伪代码。

Answer 2

快速排序非常适合于多线程处理。

分区时，分区的一端在当前线程中排序，另一端在新线程中排序。

Answer 3

由于您使用的是core2duo，因此我将研究一种并行快速排序算法。它可以就地排序，节省内存，并且可以在最多少量处理器的情况下实现与处理器数量成比例的性能提升。

并行快速排序算法基本上执行分区步骤，然后在单独的进程中对左子列表和右子列表执行快速排序。这可以通过在共享堆栈中存储边界来实现，如果使用更大的线程数量运行，共享堆栈最终会成为争用点。

还有其他算法，比如PSRS，可以扩展到更高数量的处理器，但由于您使用的是core2duo，这可能会使您最多拥有2个真正的内核+两个超线程内核，PSRS所需的额外内存可能会是一种浪费。给定要排序的元素的数量，您可能需要节省内存。

我已经在Github上用Java实现了这两种方法。如果您愿意查看代码作为使用pthread实现某些东西的指南，请告诉我。