Simplemente haz un ordenamiento basado en el índice de elementos obtenidos partiendo cada elemento por el caracter delimitador ";", una forma de aplicar de manera simplificada lo que acabo de mencionar sería usando LINQ:

Dim items As String() = {
    "052;Juan;Lopez;México",
    "101;Enrique;Morales;Guatemala",
    "005;John;McCain;USA",
    "034;María;Delgado;España"
}
 
Dim sorted As IEnumerable(Of String) =
    From item As String In items
    Order By item.Split(";"c)(0)
 
For Each item As String In sorted
    Console.WriteLine(item)
Next

---

Pero, la solución más apropiada sería que no uses un Array, sino una colección de un tipo personalizado donde encapsular la información de manera "individual" u organizada, como por ejemplo...:

<Serializable>
Public NotInheritable Class Person
 
    Public ReadOnly Property Index As String
    Public ReadOnly Property Name As String
    Public ReadOnly Property Surname As String
    Public ReadOnly Property Country As String
 
    <DebuggerNonUserCode>
    Private Sub New()
    End Sub
 
    <DebuggerStepThrough>
    Public Sub New(ByVal index As String,
                   ByVal name As String,
                   ByVal surname As String,
                   ByVal country As String)
 
        Me.Index = index
        Me.Name = name
        Me.Surname = surname
        Me.Country = country
 
    End Sub
 
End Class

Dim persons As New List(Of Person)
persons.Add(New Person("052", "Juan", "Lopez", "México"))
...

Y entonces, para ordenar ascendentemente puedes specificar la propiedad que desees:

Dim sorted As List(Of Person) = 
    persons.OrderBy(Function(p As Person) p.Country).ToList()

Saludos.