RFR 8014076: Arrays parallel and serial sorting improvements

[Doug Lea]

On 05/08/13 04:57, Chris Hegarty wrote:
> Doug,
>
> David raises a good question here. Is this implementation detail still correct:
>    "The algorithm requires a working space equal to the size of the
> original array."

All sort methods require working space of at most the size of the array
segment (which is the size of the array in the methods without
subrange bounds). This is also true for the non-parallel sorts.
(One of the changes is to DualPivotQuickSort, to use size
of segment, not size of array when it allocates).
The only difference is that the parallel sorts ALWAYS allocate
working array space, but the non-parallel ones sometimes
don't. (DualPivotQuickSort usually does not; TimSort usually
allocates less than segment size.)

I'm not sure of the best way to convey this across all
of the sort methods, especially since the "parallel"
sorts use sequential sorts when arrays sizes are smaller
that the threshold. (Aside: Sorting is unlike java.util.streams
about this. For sorting, we can make a decision about when
inter-thread memory contention and parallelization overhead
outweigh benefits. For streams, if a users says "parallel()"
we must parallelize even if it causes worse throughput.)


>   (I believe lambda's version of Arrays was not sync'ed with TL after
> integration of parallelSort, and before Doug did his work. Or at least there was
> some confusion about the latest version of this file).

Yes, sorry not to have realized that these were different when I
put in the algorithms to support stable parallel sorts.

-Doug