The sorting is most important when generating the p2sh address. The obvious thing to do to me is to sort the public keys for every new address. That way, when given the same set of public keys, the same p2sh address is always generated. Using the sort order of the original extended public keys would not allow one to find the correct address from just the public keys for that address.