# Sorting two arrays simultaneously

#### Posted on August 12, 2014

##### Last updated on August 12, 2014

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:

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.

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:

Markdown SHA1: 94d8ff6e6a38406ce1ec184408b2d3a7eb606aaf