Java : getting sorted order of Objects

I think the easiest solution, just using the standard library, would probably be:

<T extends Comparable<? super T>> int[] getSortedIndices(List<? extends T> list) {
  return getSortedIndices(list, Comparator.naturalOrder());
}

<T> int[] getSortedIndices(List<? extends T> list, Comparator<? super T> comparator) {
  return IntStream.range(0, list.size())
      .boxed()
      .sorted(Comparator.comparing(list::get, comparator))
      .mapToInt(i -> i)
      .toArray();
}

That unfortunately boxes then unboxes each index. Also the Stream.sorted operation is stateful, so there might be memory concerns for large lists. If you profile either of those things to be a problem then you can try to implement a solution that sorts an int[] based on the elements of the list. Something like:

<T extends Comparable<? super T>> int[] getSortedIndices(List<? extends T> list) {
  return getSortedIndices(list, Comparator.naturalOrder());
}

<T> int[] getSortedIndices(List<? extends T> list, Comparator<? super T> comparator) {
  int[] indices = new int[list.size()];
  // Initialize values: indices[i] = i
  Arrays.setAll(indices, IntUnaryOperator.identity());

  // Sort 'indices' based on elements of 'list'
  boolean swapped;
  do {
    swapped = false;
    for (int i = 1; i < indices.length; i++) {
      int j = indices[i - 1];
      int k = indices[i];
      if (comparator.compare(list.get(j), list.get(k)) > 0) {
        indices[i - 1] = k;
        indices[i] = j;
        swapped = true;
      }
    }
  } while (swapped);

  return indices;
}

Note that example uses Bubble Sort which is O(n^2); you will probably want to use a different sorting algorithm. There's likely a library out there that provides a way to sort an int[] with a custom Comparator so you don't have to implement it yourself. Though if you implement it yourself you might be able to find a way to avoid the cost of initializing the indices array (Arrays::setAll in the example).

Finally, be aware that both examples above expect the List to be random-access in order to perform well. An example of a random-access list implementation is ArrayList. Such implementations should implement the RandomAccess interface. If the list is not random-access (whether it implements RandomAccess or not) then the calls to get will no longer be O(1).

What you are trying to do does not make much sense. To obtain the “positional” value of a given item, you must sort the list. If you do so (by creating a new list), you can use it as a map, obtaining its value with mySortedList.indexOf( myObject );.

If large lists might even be remotely a concern:

Method 1, Wrapping:

• Wrap each Item into a Pair class, like Map.Entry with key and value
• You can also write your own Wrapper class/record (Containing the data and the index), with member variables value and originalIndex
• And add those to a Collection like ArrayList
• Have the comparator NOT target the Entry, but within it the key or value property (or originalIndex if you use a custom wrapper)

Method 2, Mapping, if you can exclude duplicates in your data:

• Set up a TreeMap<type, Integer> with a type according to your data
• add all items to that TreeMap tm, with tm.put(key, value) the values as a counting insertion index
• when you need to access the data, you can iterate over tm.entrySet(), and each entry contains your value and the original index

Method 3, Multi-Mapping:

• use a TreeMap<Iterable<type>, Integer>, then basically proceed like with the mapping solution. Best would be a TreeMap<ArrayList<type>, Integer>
• use tm.computeIfAbsent() to get/create lists inside that map
• unrolling this (accessing the data) is also easy, you just have to do it in two loops: the outer loop like above, over .entrySet(), the inner one over the list you get inside each EntrySet