merge sortとの両方quick sortが並行して動作できます。問題を 2 つのサブ問題に分割するたびに、それらのサブ問題を並行して実行できます。ただし、最適とは言えません。
4 つの CPU があるとします。最初の反復では、問題を 2 つのサブ問題だけに分割し、2 つの CPU がアイドル状態になっています。2 回目の反復ではすべての CPU がビジーですが、3 回目の反復では十分な CPU がありません。したがって、アルゴリズムを次の場合に適応させる必要がありますCPUs << log(N)。
それは理にかなっていますか？これらのケースにソートアルゴリズムをどのように適応させますか?