sorting and stability

[Doug Lea]

On 03/27/13 12:05, Doug Lea wrote:

>
> * The previous versions required temp workspace
> arrays as large as source array, even if only a
> portion was being sorted. Now they don't.

Except (and this took an embarrassingly long time to
track down), DualPivotQuickSort itself (as of JDK7)
sometimes creates a temp array, and if so, allocates
it to be as long as the array, not the slice. Now fixed.
This led to crazy anomalies during tests that made me suspect
all kinds of other problems with parallel versions.
As a side benefit though, it did lead to a few minor
improvements made while rechecking everything except
what I should have been looking at.

Another implementation note:
While I cleaned up some of it, Arrays.java and
the internal DualPivotQuickSort, TimSort, and
ComparableTimSort classes are still inconsistent about which
side does range checks and call conversion into
internal forms vs propagating convenience methods.
Someday this should be straightened out, so that
only Arrays.java does these, calling only expanded internal
forms in the sorter classes. Hilariously, this requires
that method rangeCheck be removed from TimSort.

Paul Sandoz: Please find sorts2.tar in the usual place.

-Doug