performance - 多线程编程的最佳排序算法是什么？

Question

我想对长度为 1.000.000 到 100.000.000 的整数数组进行排序。我想使用 pthread 库在具有 2Mb 缓存的 core2duo 计算机上运行该程序。我想要最快的算法!

我写了一个使用归并排序算法的半并行排序代码。但是还不够快!

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

Answer 1

我上大学已经有一段时间了，但我似乎记得 PSRS 算法对这类事情很有用。我相信谷歌会揭示大量的实现/伪代码。