If you're expected to keep the indexes lined up with the other two arrays, you're in a world of hurt.
The first thing I'd do is create an object to hold one element from each array (at the same index, of course). Next, I'd put thos objects into a generic list. Next, I'd use this tip/trick to sort on the desired property:
A Generic Comparison Class for Collection Items[
^]
Finally, I'd put the values back into the arrays in the new order (if required).
Your current design is a freakin' nightmare.