O(N log N), O(N) if already sorted.

Rather than sorting the inputs, I would sort the indexes. That way, you wouldn't need an extra hash an array, just an array.