On Nov 27, 2018, at 9:49 AM, Brian Goetz <brian.go...@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