クイックソートは目的の配列を分割し、分割した配列をそれぞれ独立にソートするので並列化はしやすいです。クイックソートを実行するスレッドにおける唯一の同期は分割した配列のソートが終わるのを待つ部分だけです。
1 let qsort cmp arr =
2 let rec qsort lo hi =
3 if hi - lo > 0
then
4 begin
5 let mid = (lo + hi)
lsr 1
in
6 if cmp arr.(mid) arr.(lo)
then swap arr mid lo;
7 if cmp arr.(hi) arr.(mid)
then
8 begin
9 swap arr mid hi;
10 if cmp arr.(mid) arr.(lo)
then swap arr mid lo
11 end;
12 let pivot = arr.(mid)
in
13 let i =
ref (lo + 1)
and j =
ref (hi - 1)
in
14 while !i < !j
do
15 while not (cmp pivot arr.(!i))
do incr i
done;
16 while not (cmp arr.(!j) pivot)
do decr j
done;
17 if !i < !j
then swap arr !i !j;
18 done;
19 let u = Thread.create (qsort lo) (!i-1)
in
20 let v = Thread.create (qsort (!i+1)) hi
in
21 Thread.join u;
22 Thread.join v
23 end in
24 qsort 0 (Array.length arr - 1);;
20 行目と 21 行目を入れ替えても正しい答えは得られますが、あまり意味がないでしょう。配列の前半分がソートされてから後半分のソートが始まるので、動作はシーケンシャルなプログラムと同じになりますが、スレッドの生成の分だけ実行が遅くなります。
並列クイックソートを実際のプログラムで使う場合には、配列の長さがある程度よりも小さくなったらスレッドを作らずにシーケンシャルにソートしたほうが良いでしょう。
* * *