マルチスレッドプログラミングに最適なソートアルゴリズムは何ですか？

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にいるので、私はParallel Quicksortアルゴリズムを見ていきます。それはインプレースでソートし、メモリを節約し、少数のプロセッサまでプロセッサの数に比例した性能向上を達成することができます。

パラレルクイックソートアルゴリズムは、基本的にパーティションステップを実行し、別のプロセスで左右のサブリストをクイックソートします。これは共有スタックに境界を格納することで実現できます。共有スレッドは、スレッド数が多いほど競合するポイントになります。

さらに多くのプロセッサーに対応するPSRSなどのアルゴリズムがありますが、コアツールの2つの真のコア+ 2つのハイパースレッドのコアで最大限のパフォーマンスを発揮するため、PSRSに必要な余分なメモリおそらく無駄だろう。ソートしようとしている要素の数があれば、おそらくメモリを節約する必要があります。

私は両方のJavaをGithubで実装しました。 pthreadを使って何かを実装するためのガイドとしてコードを見てみたいと思ったら教えてください。