If the bottleneck is on the sorting step, try using Sort::Key:

use Sort::Key qw(nkeysort_inplace);

nkeysort_inplace { /(\d{2}):(\d{2}):(\d{2})\.(\d{3})/ and "$1$2$3.$4" 
+} @lines;
[download]