One way to do it (this is a standard technique called a Schwarzian Transformation) all in one go:

my @sorted_array = 

    map { $_->{line} }  # extract the lines again 

      sort { # do the sorting
             $a->{ts} <=> $b->{ts} || $a->{letter} cmp $b->{letter}
           }  

       map { # build a data-structure that we can sort on
             my ($ts, $letter) = split / /;
             { line => $_, ts => $ts, letter => $letter }
           }   

         @array_to_sort;
[download]

This assumes you want to first sort on timestamps (numerical order) and then on the letters (string-order).

Tweak the sort expression accordingly if you require something else.