一つの二次元配列に入ったデータをソートするのではなく、二つの互いに関連するデータが格納された配列をソートするのであれば、Array.Sortメソッドを使うことが出来ます。 Array.Sortメソッドには配列を二つ引数にとるバージョンのオーバーロードが用意されていて、これを用いると一方の配列の値をキーとしてもう一方の配列をソートすることが出来ます。 これは基本型のソートと昇順・降順でのソート §.Dictionaryのソートでも解説しているもので、キーと値の関係にある二つの配列をソートするために使えます。

次の例では、このメソッドを使い、次の表のようにIDと名前からなるデータをそれぞれ個別の配列に格納し、IDの順に名前の配列をソートしています。

ID (int[]) Name (string[])
5 "Charlie"
3 "Bob"
2 "Alice"
4 "Eve"
1 "Dave"
キー・値ペアの配列をソートする
using System;

class Sample {
  static void Main()
  {
    var ids = new int[] {5, 3, 2, 4, 1};
    var names = new string[] {"Charlie", "Bob", "Alice", "Eve", "Dave"};

    // IDをキーとして名前の配列をソート
    Array.Sort(ids, names);

    for (var i = 0; i < ids.Length; i++) {
      Console.WriteLine("{0} {1}", ids[i], names[i]);
    }
  }
}
実行結果
1 Dave
2 Alice
3 Bob
4 Eve
5 Charlie