my %hash = (
  'this_type' => { 'field1' => { REQ => 'N',
                                 POS => 34,
                                 LENGTH => 10,
                                 data => ' ' x 10,
                                 FILTER => \&default_filter() }
                 },
  'that_type' => { 'field1' => { REQ => 'Y',
                                 POS => 34,
                                 LENGTH => 10,
                                 data => ' ' x 10,
                                 FILTER => \&default_filter() },
                   'field2' => { REQ => 'Y',
                                 POS => 35,
                                 LENGTH => 10,
                                 data => ' ' x 10,
                                 FILTER => \&default_filter() },
                 },
# and a lot more records...
);

##</code><code>##

@$hash{$type}->{@sorted_keys}->{data} = @mydata;

##</code><code>##

for my $k (@sorted_keys) {
    $hash{$type}->{$k}->{data} = shift @mydata;
}