Your variable $parsed should now contain a hash ref which looks like:

{
  'employee' => [
                {
                  'empid' => '9',
                  'lname' => 'A',
                  'fname' => 'Joe'
                },
                {
                  'empid' => '3',
                  'lname' => 'W',
                  'fname' => 'Larry'
                },
                {
                  'empid' => '7',
                  'lname' => '6',
                  'fname' => 'Perl'
                }
              ]
};
[download]

So, you want to sort the array referenced by the value of the 'employee' key:

@{ $parsed->{'employee'} } = sort { 
    $a->{'empid'} <=> $b->{'empid'} 
} @{ $parsed->{'employee'} };

print XMLout($parsed, NoAttr=>1, RootName=>'employees');
[download]

This will print:

<employees>
  <employee>
    <empid>3</empid>
    <fname>Larry</fname>
    <lname>W</lname>
  </employee>
  <employee>
    <empid>7</empid>
    <fname>Perl</fname>
    <lname>6</lname>
  </employee>
  <employee>
    <empid>9</empid>
    <fname>Joe</fname>
    <lname>A</lname>
  </employee>
</employees>
[download]