This article might give you some helpful ideas.

A Fresh Look at Efficient Perl Sorting

Update: While the above is a good article on sorting, I don't think it directly answers your sorting problem :-(

This same sorting question was addressed here recently.
sorting an array mix

Chris