Sorting two arrays simultaneously

Suppose you have two arrays int[] x and int[] y which represent collectively the points (x[i],y[i]) for all valid i. How would you sort these arrays based on either the x or y values?

One solution is to cram everything together into one object, and then sort that. In Java, you might make a tuple like:

class Tuple{
  int x;
  int y;
}

and then you would sort a tuple array, Tuple[] using a custom comparator.

But when you are writing quick code (for example a programming contest), time is critical, so here is a way to sort these two arrays by y value by using a third array.

Integer[] idxs = new Integer[x.length];
for(int i = 0; i < x.length; i++) idxs[i] = i;
Arrays.sort(idxs, new Comparator<Integer>(){
    public int compare(Integer o1, Integer o2){
    return Integer.compare(y[o1], y[o2]);
    }
});

Now, we have the sorted sequence (x[idxs[i]],y[idxs[i]]) for the valid i in ascending order. The idea is simply to sort the numbers \(0 \ldots n-1\) based on the arrays you are sorting. Then simply use the array idxs to index into x and y.

With Java 8, the above is also more simply:

Integer[] idxs = new Integer[x.length];
for(int i = 0; i < x.length; i++) idxs[i] = i;
Arrays.sort(idxs, (o1,o2) -> Integer.compare(y[o1], y[o2]));