[解決済み] 並列ソートアルゴリズムの中で、最も平均的な場合分け性能を持つのはどれか？

質問

ソートは直列の場合、O(n log n)を要する。もしO(n)個のプロセッサがあれば、線形的なスピードアップを望むことができます。O(log n)並列アルゴリズムは存在しますが、それらは非常に高い定数を持っています。また、O(n)に近いプロセッサを持たないコモディティハードウェアでは適用できません。p個のプロセッサがあれば、妥当なアルゴリズムはO(n/p log n)時間かかるはずです。

直列の場合、クイックソートは平均して最高の実行時複雑性を持ちます。並列のクイックソート アルゴリズムは実装が簡単で ( はこちら と はこちら ). しかし、最初のステップは1つのコアでコレクション全体を分割することなので、うまく実行できません。私は多くの並列ソート アルゴリズムに関する情報を見つけましたが、これまでのところ、明確な勝者を指し示すものは見当たりません。

私は、8～32コアで動作するJVM言語において、100万から1億の要素のリストをソートすることを探しています。

どのように解決するのですか？

以下の記事(PDFダウンロード)は、様々なアーキテクチャにおける並列ソートアルゴリズムの比較研究です。

様々なアーキテクチャにおける並列ソートアルゴリズム

記事によると サンプルソート は多くの並列アーキテクチャで最良であるようです。

Markの年齢に関する懸念に対処するための更新です。

より斬新なものを紹介する最近の記事です（2007年のものですが、これでもサンプルソートと比較されることがあります）。

サンプルソートの改良

AA-ソート

ブリーディングエッジ（2010年頃、中には数ヶ月しか経っていないものもあります。）

並列ソートパターン

メニーコアGPUによる並列ソート

ハイブリッドCPU/GPU並列ソート

ランダムな並列ソートアルゴリズムとその実験的考察

高スケーラブルな並列ソート

自然順序を用いたN要素の並べ替え。新しい適応的な並べ替え手法

2013年の更新情報です。 2013年1月頃のブリーディングエッジを紹介します。(注：いくつかのリンクはCiteseerの論文へのもので、登録が必要です（無料）。

大学での講義。

選択と並べ替えのための並列パーティショニング

並列ソートアルゴリズム講演会

並列ソートアルゴリズム講座2

並列ソートアルゴリズム講座3



その他の資料や論文など。

適応的ビットニック・ソートに基づくメニーコア・アーキテクチャのための新しいソート・アルゴリズム

高スケーラブル並列ソート 2

並列マージ

パラレル マージ 2

オブジェクトの並列自己並べ替えシステム

逐次クイックソートと並列クイックソートの性能比較

スタンドアロンおよびクラスタ化されたSMPのための共有メモリ、メッセージパッシング、およびハイブリッドマージソート

様々な並列アルゴリズム（ソートなど）の実装を含む



GPUとCPU/GPUハイブリッドのソースと論文。

GPUアーキテクチャのための並列ソートアルゴリズムのOpenCLメソッド

グラフィック・プロセッシング・ユニットを用いたデータの並べ替え

GPU上でのソートのための効率的なアルゴリズム

メニーコア GPU のための効率的なソートアルゴリズムの設計

GPUのための決定論的サンプルソート

ビットニックソートに基づくCUDAによる高速なインプレースソート

ハイブリッドアルゴリズムによる高速なGPU並列ソート

GPUでの高速並列ソートアルゴリズム

CPUとGPUにおける高速ソート：帯域幅を気にしないSIMDソートの場合

GPUサンプルソート

GPU-ABiSort。ストリームアーキテクチャにおける最適な並列ソート処理

GPUTeraSort: 大規模データベース管理のための高性能グラフィックス・コプロセッサ・ソーティング

メニーコア GPU 上での高性能な比較ベースのソートアルゴリズム

ロードバランシングと低転送オーバーヘッドを備えたCUDA対応GPUのための並列外部ソーティング

大規模データセットのためのGPUでのソート。徹底比較

2021年のアップデート : 私はこの答えを忘れてはいませんし、コンピュータ関連のすべてのもののように、それはあまり古くなっていません。今年 (2021年) 末までのいずれかの時点で、現在のトレンドと最新技術のために更新し、リフレッシュするために最善を尽くします。