OK, I think I understand now; I hadn’t realised that separate hashes within the one array could legitimately contain the same keys with different values.

I still think a generic procedure will work, it just needs a comprehensive sorting algorithm:

#! perl
use strict;
use warnings;
use Test::More tests => 2;
use Test::Deep;

my @x = 
(
    { key_3 => 'A', key_2 => 'CC', key_4 => 'E', key_5 => 0 },
    { key_3 => 'A', key_2 => 'DD', key_4 => 'F' },
);

my @y =  
(
    { key_3 => 'A', key_2 => 'DD', key_4 => 'F' },
    { key_5 =>  0,  key_3 => 'A',  key_2 => 'CC', key_4 => 'E' },
);

cmp_deeply(        \@x,      bag(@y), 'Deep' );
print '-' x 20, "\n";
 is_deeply( my_sort(@x), my_sort(@y), 'More' );

sub my_sort
{
    my $f = sub
    {
        my @keys_a = sort keys %$a;
        my @keys_b = sort keys %$b;

        return -1 if @keys_a < @keys_b;
        return  1 if @keys_a > @keys_b;

        my $result   = 0;
           $result ||= $keys_a[$_]  cmp      $keys_b[$_] ||
                  $a->{$keys_a[$_]} cmp $b->{$keys_b[$_]} for 0 .. $#k
+eys_a;

        return $result;
    };

    return [ sort $f @_ ];
}
[download]

(For the basic idea, see How-do-I-sort-an-array-by-anything of perlfaq4.) Output:

14:38 >perl 1314a_SoPW.pl
1..2
ok 1 - Deep
--------------------
ok 2 - More

14:38 >
[download]

Disclaimer: I’ve tested this only minimally; there may be corner cases I haven’t found. But I think this should allow you to return to using Test::More::is_deeply to get the benefit of its superior failure messages.

Hope that helps,