Here's one way: step through the array N elements at a time, sorting each subset as you go using the "Schwartzian Transform".

use strict;

my $N = 5;

my $arr = [
  '1 - foo - xxx',          
  '5 - foo - abc',          
  '4 - foo - efg',          
  '2 - foo - atc',          
  '3 - foo - ggg',          
  '1 - bar - aaa',          
  '2 - bar - ttt',          
  '3 - bar - xxx',          
  '5 - bar - akk',          
  '4 - bar - jjg',          
  '1 - bar - atc',          
  '2 - bar - yyg',          
  '5 - bar - gga',          
  '3 - bar - ttt',          
  '4 - bar - gag'
];    


my $nelem = @$arr;

if ($nelem%$N) {
  die "error - array length not even multiple of $N.\n";
}


for my $i (0 .. $nelem/$N-1) {
  my @temp = @$arr[$N*$i..$N*($i+1)-1];
  
  @temp = map  { $_->[1] }
          sort { $a->[0] <=> $b->[0]}
          map  { [ (my $x) = split(/\s+/, $_) , $_] } @temp;
  
  for my $t (@temp) {
    print "$t\n";
  }
  
}
[download]