Is this at all possible with the way the keys are currently created?

Yes, of course. See the last example of How do I sort an array by (anything)? as a guide.

Would it simply be easier to use a multidimensional hash and then nested loops to try and handle accessing the elements?

Conceivably. However, I think the simplest approach is to extract a single sortable number from each key which you could do like this:

my $index = sprintf("%i.%6.6i", split (/\t/, $key));
[download]

Whether you use this number as the actual key or just use it to sort and then reassemble is up to you.

I would take a look at our Tutorials section if I were you. A brief tutorial on Perl's native sorting facilities. helped me greatly when I was facing a similar problem.

Here's an example of what hippo was talking about. Note that it only works for positive integers in the range 0 .. 4,294,967,295.

c:\@Work\Perl\monks>perl -wMstrict -le
"use Data::Dump qw(dd);
 ;;
 my @raw_keys = (
   '1    12301    A    B',
   '2    4501    A    B',
   '1    12299    E    F',
   '2    4502    C    D',
   '1    12310    A    B',
   '2    4499    C    D',
   '2    15410    A    B',
   );
 ;;
 my $ornament = 'N N';
 my $decorate   = qq{  $ornament  a*};
 my $undecorate = qq{x[$ornament] a*};
 ;;
 my @sorted_keys =
   map unpack($undecorate),
   sort
   map pack($decorate, (split ' ', $_, 3)[0,1], $_),
   @raw_keys
   ;
 dd \@sorted_keys;
"
[
  "1    12299    E    F",
  "1    12301    A    B",
  "1    12310    A    B",
  "2    4499    C    D",
  "2    4501    A    B",
  "2    4502    C    D",
  "2    15410    A    B",
]
[download]

You should be able to access the keys using keys and store them in an array, and then write a sort routine to priority sort by your first number then your second number extracted from each of those key using split and taking a slice of just the two numbers you want to sort by.