Get the indices of an array after sorting?

Suppose the user enter an array, for example:

Array = {France, Spain, France, France, Italy, Spain, Spain, Italy}

which I did know the length of it

the index array would be:

index = {0, 1, 2, 3, 4, 5, 6, 7}

Now, after sorting it using Arrays.sort(Array);

newArray will be like:

newArray = {France, France, France, Italy, Italy, Spain, Spain, Spain}

and the newIndex will be:

newIndex = {0, 2, 3, 4, 7, 1, 5, 6}

The problem is: how can I find the newIndex from the input Array?

Answer

Don’t sort the array to start with. Sort the index array, passing in a comparator which compares values by using them as indexes into the array. So you end up with newIndex as the result of the sort, and it’s trivial to go from there to the sorted array of actual items.

Admittedly that means sorting an array of integers in a custom way – which either means using an Integer[] and the standard Java library, or a 3rd party library which has an “IntComparator” interface which can be used in conjunction with a sort(int[], IntComparator) type of method.

EDIT: Okay, here’s an example comparator. For the sake of simplicity I’ll assume you only want to sort an “original” array of strings… and I won’t bother with nullity testing.

public class ArrayIndexComparator implements Comparator<Integer>
{
    private final String[] array;

    public ArrayIndexComparator(String[] array)
    {
        this.array = array;
    }

    public Integer[] createIndexArray()
    {
        Integer[] indexes = new Integer[array.length];
        for (int i = 0; i < array.length; i++)
        {
            indexes[i] = i; // Autoboxing
        }
        return indexes;
    }

    @Override
    public int compare(Integer index1, Integer index2)
    {
         // Autounbox from Integer to int to use as array indexes
        return array[index1].compareTo(array[index2]);
    }
}

You’d use it like this:

String[] countries = { "France", "Spain", ... };
ArrayIndexComparator comparator = new ArrayIndexComparator(countries);
Integer[] indexes = comparator.createIndexArray();
Arrays.sort(indexes, comparator);
// Now the indexes are in appropriate order.