Extending Java Arrays/Collection Sort API

[Brian Goetz]

Doug is right that there is an enormous potential list of sort methods, 
and we can't include them all.  But I do miss the ability to extract 
indexes instead of sorting the array itself.

On 11/14/2018 3:01 AM, Laurent Bourgès wrote:
> Hi,
>
> I am a scientist and the author of the Marlin renderer, integrated in
> OpenJDK.
>
> In this renderer, I needed a fast sort algorithm on small almost sorted
> arrays, but more important, to deal with 2 arrays: x values and their
> corresponding edge indices (pointer like). I derived my MergeSort class to
> perform 2 swaps (x & edge ptr) as Arrays.sort() or TimSort() did not
> provide such API.
>
> 1. I started discussing about extending the Java Sort API with Vladimir
> Yaroslavskiy, the author of the famous Java DualPivotQuickSort, as he is
> currently improving it.
>
> His coming DPQS 2018 class provides lot of sort algorithms, I propose to
> make them public API through a facade method in Arrays class:
> insertionSort(), heapSort(), mergeSort(), quickSort()... Of course, his
> current code is dedicated to DPQS, but his algorithm implementation could
> be generalized to propose the Best implementations as a public Java API
> (stable & unstable sorts)
>
> For example in Marlin, I need trivial insertionSort() in the Helpers class,
> my MergeSort could be replaced by another best implementation.
> Let's not reinvent the wheel...
>
> 2. New Sort API to deal with indices...
>
> For now, there is no mean to obtain the indices sorted on another value,
> see my introduction: edge indices sorted by their x positions.
> In data science, this is very useful and general.
>
> What about an Arrays API extension:
> - Arrays.sort(int[] a, int[] b, low, high) or
> Indices int[] Arrays.sortIndices(int[] a, low high), a[] left untouched
> - same with preallocated buffers & runs arrays
> - alternatively, it could be expressed as Comparator<Primitive>
> Arrays.sort(int[] a, low, high, Comparator<int, int> cmp) that sorts array
> a using the given comparator. For example, a[] could be edge indices sorted
> according to their edge x position...
> This comparator is specific as it compares anything (external storage) at
> given indices i,j.
>
> Finally Marlin renderer would benefit from Value types (array of structs),
> as edge data are currently packed in int[] arrays, but this new Sort API
> seems to me general & needed enough to be discussed here.
>
> Best regards,
> Laurent