現在、CSVファイルの束を読み込んで、CSVファイルのすべてのデータからなる1つの大きなソートCSVファイルを出力するマルチスレッドソーターを作成しています。今は、mergesortを使用して個々のスレッドの各CSVをソートし、最後にスレッドのすべてのデータを連結してソートすることを計画しています。私はちょうどmergesortを使用することが "速い"と考えられるかどうか不思議です。スレッドがソートされたデータを連結した後、データは個々のセクションでソートされますが、全体的にソートされません。最も速いマルチスレッドソート方法
データの量はどれくらいですか？ソートはO(n log n)であり、本質的に並列化できない最後のマージステップはもちろんO(n)なので、log nがまったく巨大でないか、またはデータの移動コストと比較して比較コストが不当に大きくならない限り、マルチスレッドではほとんど得られませんソート。
まだ試してみたいのであれば、あなたのアプローチで間違っているのは、連結リストの最終的なマージソートです。基本的には、ソート全体をもう一度やり直すのと同じスピードになるでしょう。代わりに、マージソート全体ではなく、単一のマージ操作を使用して、スレッドの各ペアからの出力をマージします。これを繰り返して、毎回ソートされたリストの数を半分にして、最後のステップで2つのリストをマージします。この作業をスレッドに分割するには、階層内の2つの「兄弟」スレッドがジョブを終了したときに、一方が終了し、もう一方が階層内で「上に移動」し、その兄弟の出力をマージするスレッド間の階層関係を設定します。
私は第1段落の議論に同意しません。マージソートの各パスはほぼ同じ時間がかかります（以前のパスはより多くのマージを行う必要があり、後のパスは大きなリストでマージする必要があるため）。したがって、log nが比較的低い場合でも25（約34Mアイテムを意味する） - 早期パスの並列化は合計時間にかなり大きな影響を及ぼす可能性があります。 – ruakh
各ファイルには28の列と約5000行があります。ファイルの量は1〜1024の範囲です。 – codemonkey
スレッドを開始するよりも短い時間で50000行（多くの場合10倍）をソートできます。マルチスレッドのソートは、何十億もの行を持たない限り、遠隔地でも意味をなさないでしょう。 –
マージソートは、マルチスレッドのボトムアップマージソートを行うまで、マージ関数内の比較的タイトなループのためにメモリにバインドされると考えました。 4つのスレッドでは、シングルスレッドのマージソートの約3倍の速さでした。この例では、配列は4つの部分に分割され、各部分はマージソートされ、次にスレッド0は1/4配列0と1をマージし、スレッド2は1/4配列2と3をマージし、スレッド0は2つのハーフ配列をマージします。
https://codereview.stackexchange.com/questions/148025/multithreaded-bottom-up-merge-sort
テキストファイルの一種であるGNUソートは、初期の一時ファイルを作成するために使用される最初のパスでポインタの配列にマルチスレッドマージソートを行い（元のファイルを想定するよりも大きいです使用可能なメモリ）。最初のパスの後、ボトルネックにはプロセッサの速度ではなくディスクのI/O速度があるため、一時ファイルにはシングルスレッドの16ウェイマージが行われます。
これは良い解決策のように思えます。私は個々にソートされた配列とmergesortingを連結することを計画していましたが、それは本質的にマージソートの最後のステップにあるので時間を無駄にしています。今は、ファイルの個々の構造体配列をまとめて保持するために、リンクされたリストを使うべきか、別の配列だけを使うべきかについて考えています。 – codemonkey
@codemonkey - リンクリストを使用する代わりに、構造体へのポインタの配列を使用できます。 – rcgldr
[適応ソート]（https://en.wikipedia.org/wiki/Adaptive_sort）についてお読みください。 – ruakh
私は最速についてはわかりませんが、[ここ]（https://stackoverflow.com/a/11380649/315052）は実装です。 – jxh