This is a fairly common problem. The solution is to not use a string as a record, but to use a composite data type like an array or a hash as the record, sort that, and then construct your string from the record when its needed. The below is a version of this, where the string is actualyl part of the record. We sort the list of records, and then extract the strings from the resulting set.

@lines = split(/\n/,$space{ $host });

shift @lines;
my @recs;
foreach $disk_used (@lines)
{
     $_ = $disk_used;
     if (/(\/\w+\/\w+)\s+\w+\s+\d+\s+\d+\s+(\d+)\s+(\d+)%/ )
     {
           $free = 100-$3;
           push @recs,[$host,$1,$2,$free,"$host:$1     $2      $free%"
+];
     }
}
@out=map { $_->[-1] } sort { $b->[3] <=> $a->[3] } @recs;
[download]

HTH