“XML vs. JSON” is entirely up to you ... generally, I prefer to make as few “disruptive changes” as possible.   Furthermore, in both cases, you wind up at the same place:   with (I presume ...) a Perl array of Perl hashrefs.   The question before the court has to do with sorting, not with how the structure-to-be-sorted came to be.

As you will see from perldoc -f sort, the sort function takes as one of its parameters a code-block (or a subroutine reference) which does the actual comparison.   It returns a value less-than, equal-to, or greater-than zero, and Perl provides two operators, <=> and cmp, to do that, for numeric and string values, respectively.   When sorting by more than one field, the || operator is used, as the perldoc specifically shows.   Therefore, this is how you sort your data ... no matter how intricate its structure is, and no matter how the Perl data structure that you are sorting came to be.

In the case of XML data, sorting can also be requested using an XPath expression, but not, IIRC, with XML::Simple.