Not clear why you want to do this (less memory usage maybe?), but one way of eliminating $Record would be to store your top N results in a hash, as follows. This means you still need to record 40 entries from $Record, but that's fewer than a thousand, right? An explanation of your motivation might help…

my %results;
foreach (1 .. 40) {
    my $hit = int rand(30);
    my $id = int rand(1000);
    $results{$id} = [ $id, $hit ]; # Store ID and hit in array
}

foreach (0 .. 999) {
    my $data = int rand(100);
# Only stack data we're interested in:
    if(exists($results{$_})) {
      push @{$results{$_}}, $data;
    }
}
# Sort by descending hit (array[1] entry):
my @search_results = sort { $b->[1] <=> $a->[1] } values %results;

foreach (@search_results) {
    my ($hit, $id, $data) = @$_;
    print "$hit $id $data\n";
}
[download]

… and if you're into more variable elimination, @search_results can go easily too — but since it's an array of array references, it takes up next to no space so you'd lose clarity for little gain.

The [ $id, $hit ], @{$results{$_}}, $b->[1] and @$_ stuff are all explained in the Perl references documentation (“perldoc perlref”).

I think results are better in an array of arrays, this also gets rid of a warning from sort on non numeric data if you use warnings (hint, use warnings ++). I had to tweak your sort a bit, Here is a frag to show this

#!/usr/bin/perl
use warnings;
use strict;

my @results;
for (1..40){
    my $hit = int rand(30);
    my $id = int rand(1000);
    push @results, [$hit, $id];
}

my @search_results = sort { $b->[0] <=> $a->[0] } @results;

print $_->[0], "\t", $_->[1], $/ for @search_results
[download]

Records (at least the example you gave) are sequential and continuous so an array looks like just the ticket

#Records
my @Record;
push @Record, int rand(100) for (0..999);
[download]

lets put it all together with a little bit of tidying up and removing a few intermediate variables and doing the sort where we need it

#!/usr/bin/perl
use warnings;
use strict;

#Search Results
my @results;
push @results, [int rand(30), int rand(1000)] for (1..40);

#Records
my @Record;
push @Record, int rand(100) for (0..999);

#Display
print "hits\t ID\t Data\n";
for (sort { $b->[0] <=> $a->[0] } @results) {
    print "$_->[0] \t $_->[1] \t $Record[$_->[0]]\n";
}
[download]

loosing the hash for records is OK as long as your records aproach a continuos sequential set easily indexed by an integer. If they are sparse, non integer (or something not easily munged to an integer value) or non-continuous a hash will be the better bet

update

as conrad++ points out below if you have a lot of IDs you may be better not reading them all in but only those you are going to display. If you are getting them from a sorted file or a DB something like the following may ring your bell. You are back to having a hash but this could be a serious saving in memory usage

# this bit is untested, 'tis bedtime for me
open DATA, "$id_file" or die "something useful";
foreach $id sort ($b->[1] <=> $a->[1] } @results) {
    # read file until $_ (the ID) is found
    while (<DATA>) {next unless /^$id->[1]/}
    # If you want to use it later
    # $record_hash{$_)=+(split /your_sep/)[1]
    # or just print the record
    my $record=+(split /your_sep/)[1]
    print "$_->[0] \t $_->[1] \t $Record\n";
}
# goodnight.
[download]

Cheers,
R.