I have gone through sorting of simple 2-D arrays. And there are ample ways to do this efficiently. But lately, I'm facing some issues in sorting 2-D arrays with the following conditions:

Suppose there's a 2-D array with 2 rows and n columns. (Here n can vary from 1 upto 10^6) . All the entries are integer entries with the upper bound being 2 * 10^9 . The task here is to sort the elements in the first row in ascending order, preferably ( although, ascending/descending doesn't make much of a difference anyway ) and the elements of second row should occupy their new positions corresponding to their previous row-1 elements ( irrespective of their relations among other row-2 elements ).

A sample:

Suppose the array is as follows:

5 6 4 8 7 3 4 9 5 1 0 2

Then after sorting the final array should become:

3 4 5 6 7 8 2 5 4 9 0 1

With the conditions of n's upper bound going as high as 10^6, trivial methods of sorting this serve useless and lead to TLE message. How can the aforementioned task be achieved in the most efficient manner?