You can use a more complex sort routine. However, any extra code there will be executed for each comparison, O(N log N) times IIRC. As you are using a Schwartzian transform anyway, just make sure that empty strings are mapped to a value that sorts last. E.g. (untested):

@sorted = map { $_->[1]  }
          sort { $a->[0] cmp $b->[0] }
          map { [ (length($all{$_}->[$sortValue])?
                  '0' . $all{$_}->[$sortValue] :
                  '1'),
                $_ ]
              } keys %all;
[download]