There are several good references in the Tutorials section of the Monestary on sorting. I would look in the subsection Getting Deeper Into Perl and the sub-subsection List Processing, Filtering, and Sorting. In particular you should look at transformational sorts; the Schwartzian Sort is, I think, one of the more popular that should meet your needs.

I would suggest, in particular, any one of three of the tutorials:

A brief tutorial on Perl's native sorting facilities by BrowserUK,

Resorting to Sorting by japhy, or

Complex sorting by vroom

The first is a good place to start, but the other two are really good, to, IMHO.

Good luck.

UPDATE: One thing I should've said (I didn't think about this until I got home last night) is that when you write your sort subroutine (which is what gives the transformation sorting...like the Schartzian Transformation sort, etc., their power...you'll need to parse each line of the input file to isolate the time data that you want to sort on. This will also mean that you'd need to read (slurp) the entire file into an array since the types of sorting mentioned in the references I posed do so in memory. There are some CPAN modules (e.g., Sort::Array) that I believe can sort files without having to slurp the entire file into memory...but I don't have any experience with them so I'm not sure if they can actually do that...maybe other Monks could guide you on that). Again, good luck.