citromatik,
I would still avoid sort.

my @sorted = map $_->[0],
    sort {$a->[1] <=> $b->[1] || $a->[2] <=> $b->[2]}
    map {
        my (undef, $val1, $val2) = split " ";
        ($val1, $val2) = ($val2, $val1) if $val2 < $val1;   
        [$_, $val1, $val2];
    } <DATA>;
# Untested
[download]