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

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

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

Class Sample
  Shared Sub Main()
    Dim ids As Integer() = New Integer() {5, 3, 2, 4, 1}
    Dim names As String() = New String() {"Charlie", "Bob", "Alice", "Eve", "Dave"}

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

    For i As Integer = 0 To ids.Length - 1
      Console.WriteLine("{0} {1}", ids(i), names(i))
    Next
  End Sub
End Class
実行結果
1 Dave
2 Alice
3 Bob
4 Eve
5 Charlie