4コアで4億件のマージソートの話。
1億件ずつ4つのブロックに分けて、それそれABCDと呼ぶ。
最初の入り口の関数がバッファを用意してコア数も確認。
再帰用の関数に全部の情報を渡す。
再帰用の関数は普通のマージソートのように半分に割って、最初はブロックABとCDに割って、
それぞれ再帰でマージソートをやらせるのだが、
ここで子スレッドを生成して子スレッドにはCDのマージソートをやらせて自スレッドはABを担当して、終われば合流してシングルスレッドでマージをする。
ABを担当することになったスレッドはこれをAとBに分けて、またスレッドを一つ生成して、子スレッドにBをやらせて、自スレッドはAを担当する。
再帰でAだけを担当する処理が開始されるが、この段階では合計4スレッドが動いてる状態なので、
これ以上はスレッド分けが不要となるため、ブロックAを担当するスレッドは普通のマージソートを使ってブロックAを処理する。
4つのブロックに対して4つのスレッドが並列でマージソートをするが、
それぞれ異なる領域を処理しているので一切のロックがない。
そして大きさが同じなので、ほぼ同時に処理が終わる。
それらが終われば、ABとCDそれぞれのjoinが行われて2スレッドになり、
ABを担当するスレッドはAとBのマージを
CDを担当するスレッドはCとDのマージをする。
最後は一つのスレッドに戻ってABとCDのマージをする。