You were very close. I adjusted indentation a little.

   sort
   {
      $href->{$b}[ 1 ]   cmp    $href->{$a}[ 1 ]  ||
                    $b   cmp    $a
   }
   keys %data;
[download]

You can chain any number of conditions with the || operator. The special globals $a and $b get the keys (e.g., 'part2') to compare.