What I have not understood is: do you want to create a sorted XML file or do you want to read the xml file and sort the data? For the latter, have a look at this:

use strict;
use warnings;
use XML::Simple;
use Data::Dumper;

my $xml = XMLin( 'depart.xml');
print Dumper $xml;
print "First level of data\n";
for my $level1 (keys %$xml) {
  print "$level1\n";
}
# assume you want flightStatuses
print "Second level of data\n";
for my $level2 (keys %{ $xml->{flightStatuses} } ) {
  print "$level2\n";
}
# only has flightStatus which is an array ref containing hashes, hint 
+'=> ['
print "Unsorted depature times\n";
for my $level3 ( @{ $xml->{flightStatuses}->{flightStatus} } ) {
  print $level3->{carrierFsCode};
  print $level3->{flightNumber},": ";
  print $level3->{operationalTimes}->{scheduledGateDeparture}->{dateUt
+c},"\n";
}
# now that we have the data we can sort
print "Sorted depature times\n";
for my $level3 ( sort 
                 { $a->{operationalTimes}->{scheduledGateDeparture}->{
+dateUtc} 
                     cmp 
                       $b->{operationalTimes}->{scheduledGateDeparture
+}->{dateUtc}  }
                 @{ $xml->{flightStatuses}->{flightStatus} } ) {
  print $level3->{carrierFsCode};
  print $level3->{flightNumber},": ";
  print $level3->{operationalTimes}->{scheduledGateDeparture}->{dateUt
+c},"\n";
}
[download]

This is only an illustration how to deal with complex structures. First you use Data::Dumper to see how the structure looks like and whether you have hashes or arrays, then you untangle it level by level, adding sorting only at the end. HTH.