From C++14 and Java 1.8

[dsimcha]

On Sunday, 21 April 2013 at 12:08:54 UTC, bearophile wrote:
> Arrays#parallelSort uses Fork/Join framework introduced in Java 
> 7 to assign the sorting tasks to multiple threads available in 
> the thread pool. This is called eating your own dog food. 
> Fork/Join implements a work stealing algorithm where in a idle 
> thread can steal tasks queued up in another thread.
> An overview of Arrays#parallelSort:
>
> The method uses a threshold value and any array of size lesser 
> than the threshold value is sorted using the Arrays#sort() API 
> (i.e sequential sorting). And the threshold is calculated 
> considering the parallelism of the machine, size of the array 
> and is calculated as:
>
> private static final int getSplitThreshold(int n) {
>   int p = ForkJoinPool.getCommonPoolParallelism();
>   int t = (p > 1) ? (1 + n / (p << 3)) : n;
>   return t < MIN_ARRAY_SORT_GRAN ? MIN_ARRAY_SORT_GRAN : t;
> }
>
> Once its decided whether to sort the array in parallel or in 
> serial, its now to decide how to divide the array in to 
> multiple parts and then assign each part to a Fork/Join task 
> which will take care of sorting it and then another Fork/Join 
> task which will take care of merging the sorted arrays. The 
> implementation in JDK 8 uses this approach:
> - Divide the array into 4 parts.
> - Sort the first two parts and then merge them.
> - Sort the next two parts and then merge them.
> And the above steps are repeated recursively with each part 
> until the size of the part to sort is not lesser than the 
> threshold value calculated above.
>>>
>
>
> I think it's worth adding something similar as strategy of 
> std.algorithm.sort.

FWIW, I created a parallel sort in D a while back using 
std.parallelism.  It was part of std.parallel_algorithm, a 
half-finished project that I abandoned because I was disappointed 
at how poorly most of it was scaling in practice, probably due to 
memory bandwidth.  If you have some expensive-to-compare types, 
though, it may be worthwhile.

https://github.com/dsimcha/parallel_algorithm/blob/master/parallel_algorithm.d