Extending Java Arrays/Collection Sort API

[John Rose]

On Nov 27, 2018, at 9:49 AM, Brian Goetz <brian.goetz at oracle.com> wrote:
> 
> 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.

Or, slightly more generally, sorting an int[] or long[] array with a comparator.
Sometimes you don't want an object per sorted entity; you want some kind
of oracle function that can compare two indexes into a non-concrete
(virtualized) set of values; the sort operation would output the reordered
ints.

Example:  Sorting indexes into a large text file according to some algorithm
such as Burrows-Wheeler.  You don't want to make all the substrings and
put them into a String[] array, and you don't even want to make CharSequence
objects that view into the text file.  You just want indexes into the text file to
be sorted.

IMO, the very simplest answer with significantly better semantics is:

  void sort(int[] a, (int[] a, int fromIndex, int toIndex, IntBinaryOperator cmp);

And maybe add parallelSort, and use a new IntComparator instead of
repurposing IntBinaryOperator.

Extracting the permutation vector of indexes from an array sorting operation
would then look like this:

    public static <T> int[] sortToIndexes(T[] a, Comparator<? super T> c) {
        int[] perm = new int[a.length];  // starts as an iota vector
        for (int i = 0; i < a.length; i++)  perm[i] = i;
        sort(perm, 0, a.length, (i, j) -> c.compare(a[i], a[j]));  // NEW PRIMITIVE
        return perm;
    }

But there are other use cases for comparator-based sorting of indexes,
which start not with an iota vector, but with an array of index-like values
which may index into something other than an array (like a text file,
which is why 'long[] a' might be useful too).

In Valhalla many such use cases can be covered by using a flat array of
values which encapsulate the integer (or long) indexes, and sorting that.
The array of wrapped primitives will look like Object[] and so the existing
API point with a comparator would allow the flat array of ints (dressed as
value Objects) to be sorted according to any ad hoc ordering rule, including
treating them as indexes.

So maybe the answer is "wait for Valhalla".  Still, the lack of a comparator
on primitive arrays is an unnecessary limitation, which excludes index-based
computations from the portfolio of our sort methods.

— John