You want the following things to occur in the order in which they are listed:

• Shuffle
• Limit
• Sort

I don't think you can do things in that order with a simple SELECT query, although you could probably do the first two use a subquery. (I'm guessing, my SQL is rusty.) Alternatively, Perl can be your "second layer".

Replacing
return {catrand => \@output};
with
return {catrand => [ sort { $a->{Cat} cmp $b->{Cat} } @output ]};
would do the trick.