This is kinda tested. I would test it thoroughly with your data before using it in production.

sub by_my_criteria
{
    return 1 unless length $a->[0];
    return -1 unless length $b->[0];
    return $a->[0] cmp $b->[0];
}

sorted = map { $_->[1]  }
      sort by_my_criteria
      map { [ $all{$_}->[$sortValue], $_ ]
          } keys %all;
[download]

Update: Fixed by_my_criteria() as per tadman's comments via /msg.

------
We are the carpenters and bricklayers of the Information Age.

Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.