You delegate the comparison logic to cmp but cmp is not psychic.

Your dates seem to be parsable by this module DateTime::Format::x509 (if you omit the day-name). So first try to parse the date of each log-line and create a DateTime object from it. Like so (straight from the manual):

use DateTime::Format::x509;
 
my $f = DateTime::Format::x509->new();
my $dt = $f->parse_datetime('Mar 11 03:05:34 2013 UTC');
[download]

If your log files all come from a single timezone then just use any timezone (e.g. UTC) string in calling parse_datetime() (I do not see timezone information in your logs).

First create a parser obj before any date parsing:

my $dtparser = DateTime::Format::x509->new();
[download]

Then, in the loop of reading log-lines I would change  push @lines, "$line\n"; to:

$line =~ /^\<\d+\>\w+\s+\d+:\d+:\d+\s+\w+:TIMESTAMP\=\w+\s+(\w+\s+\d+\
+s+\d+:\d+:\d+\s+\d+).*MSGCLS.*$/m;
$datestr = $1; # I use your regex but with day-name removed from brack
+et, e.g. Oct  5 04:08:28 2018
my $dtobj = $dtparser->parse_datetime($datestr);
my $epoch = $dtobj->epoch();
push @lines, [$line, $epoch]; # Line AND epoch saved into the array, m
+aybe dtobj too for completeness
[download]

Now you can compare the epochs numerically:

@sortedlines = sort { $a->[1] <=> $b->[1] } @lines;
[download]

Bonus: note how in the way you do the comparisons, each time you compare 2 lines a regex needs to be applied for each line in order to extract date-string. This means that in comparing Line1 with Line2, Line1 with Line3 and Line2 with Line3 you applied the regex 6 times whereas 3 times would have been sufficient! That's why before sorting it is best to transform the data to the actual comparison format (e.g. the date-string) first before running sort. In this way you save processing time (in the expense of some space).

Edit: haukex's answer mentions the above more succinctly (and beat me to it by a few minutes).

bw, bliako