The sort function is sorting them correctly based on the elements being strings. If you desire a different sort order then you might want to look at creating a customised implementation of IComparer.
The following snippet should give you a basic idea.
Class Testing
Implements IComparer
Public Function Compare(ByVal x As Object, ByVal y As Object) As Integer Implements System.Collections.IComparer.Compare
Dim x1 As String, y1 As String
x1 = DirectCast(x, String)
y1 = DirectCast(y, String)
Dim i1, i2 As Integer
i1 = Integer.Parse(x1.Substring(1))
i2 = Integer.Parse(y1.Substring(1))
If i1 > i2 Then Return 1
If i1 < i2 Then Return -1
Return 0
End Function
End Class
This can then be called from a method like
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim a() As String = {"a1", "a10", "a3"}
Dim x As IComparer
Array.Sort(a, New Testing)
End Sub