Sorting hashes on value length whilst preserving order

One possible solution

You can save the position of the line in the input file handle as well as the length. The $. magic variable (input line number) provides this. You can then sort on both values.

use strict;
use warnings;

my %lines;
while ( my $curr_line = <DATA> ) {
  chomp($curr_line);
  $lines{$curr_line} = [ length $curr_line, $. ];
}

for my $line (
  sort {
       $lines{$a}->[0] <=> $lines{$b}->[0]
    || $lines{$a}->[1] <=> $lines{$b}->[1]
  } keys %lines
) {
  print $line, "\n";
}

__DATA__
tiny lin1
medium line
big line
huge lin2
rand lin3
megahugegigantic line

This will always output

big line
tiny lin1
huge lin2
rand lin3
medium line
megahugegigantic line

You can of course use a hash to make the code more readable, too.

$lines{$curr_line} = { 
  length   => length $curr_line, 
  position => $., 
};

Explanation of your implementation

Your results changed their order every time because of random hash ordering. The way keys returns the list of keys is random, because of the way Perl implements hashes. This is by design, and a security feature. Since there are several keys that have the same value, the sort will sometimes return different results, based on which of the equal value keys came out first.

You could mitigate this by sticking another sort in front of your keys call. That would sort the keys by name, at least making the order of the undesired result be consistent.

#                                               vvvv
for my $line (sort{ $lines{$a} <=> $lines{$b} } sort keys %lines) { ... }

Note that you don't have to chomp the input if you put the \n back when you print. It's always of the same length anyway. If you do, you should print a $/, which is the input record separator that chomp removed, or you falsify your data.

Your problem is not with sort Perl uses the quick sort algorithm which is a stable sort, inputs that match the same sort key have the same order on output of the sort as input.

Your problem is that you are storing the lines in a hash. A hash is an unordered collection of key value pairs so adding the lines to the hash and then printing them out again with out the sort will give you the lines in a random order.

You need to read all the lines into an array and then sort them on length, the quickest way being to use a Schwartzian Transformation see below.

my  @lines = <STDIN>;
chomp(@lines);

my @sorted = # This is the clever bit and needs to be red from the last map up
    map { $_->[0] } # Get the lines
    sort { $a->[1] <=> $b->[1] }  # Sort on length
    map { [$_, length $_] } # Create a list of array refs containing
        # the line and the length of the line
    @lines;

print join "\n", @sorted; # print out the sorted lines

Nowhere do you store the original order, so you can't possibly sort by it. The easiest fix is to store the lines in an array, and ensure that Perl is using a stable sort.

use sort 'stable';

my @lines = <>;
chomp(@lines);

for my $line ( sort { length($a) <=> length($b) } @lines) {
   say $line;
}

[ ST is overkill for this. It' such overkill that it probably even slows things down! ]

As has been explained, the randomness comes from your use of hash keys to store the strings. There is no need for this, or anything more elaborate like a Schwartzian Transform, to make this work

All Perl versions since v5.8 have used a stable sort, which will keep values that sort equally in the same order. But you can insist that the sort operator you get is a stable one using the sort pragma with

use sort 'stable'

Here's how I would write your program. It stops reading input at end of file, or when it sees a blank line in case you want to enter the data from the keyboard

use strict;
use warnings 'all';
use feature 'say';
use sort 'stable';

my @list;

while ( <> ) {
    last unless /\S/;
    chomp;
    push @list, $_;
}

say for sort { length $a <=> length $b } @list;

Using the same input as you use in the question, this produces

output

big line
tiny line
huge line
rand line
medium line
megahugegigantic line