In any sort routine (and there are dozens of examples on the net) there is a point at which you compare two items, and another point at which you swap two items.
In this case, you would compare the (,1) elements, but swap both the (,0) and (,1) elements if called for.
Often it's better to use a separate one-dim index array with identical bounds as the (0,) dimension of the two-dim array. Compare and swap 'through' this array, so that your data array remains unchanged but can be accessed in sorted order.
But I would never use the arrangement you show to begin with. I would either construct a user-defined type that has the appropriate data type for each element, and create a one-dim array of that. Or a class that contains the data, and has an Index array property and a Sort method that will arrange the Index in the order you like.