foreach $key ( sort {$b <=> $a} values %memhash){
here $key is not the hash key, it is one of the values!

foreach my $key sort{$memhash{$a} <=> $memhash{$b}}keys %memhash
would sort keys according to the values of those keys

At the root of your problem is the conversion from array to hash is flawed. However, I don't see why you need a hash. You can just sort your array.

#!/usr/bin/perl -w
use strict;

my @array = <DATA>;
@array = sort {my $mema = (split(' ',$a))[0];
               my $memb = (split(' ',$b))[0];
                    $mema <=> $memb
               }@array;
               
print @array;
print "\n";

#to get >500000, use grep
print grep{(split)[0] > 500000}@array;

=prints
104272 - disp+work.exe 10208 0
119540 - disp+work.exe 6376 0
119728 - SavService.exe 2336 0
159176 - disp+work.exe 7292 0
199288 - disp+work.exe 7760 0
255120 - disp+work.exe 4548 0
276124 - disp+work.exe 8948 0
283332 - disp+work.exe 9620 0
327372 - disp+work.exe 7892 0
350060 - disp+work.exe 9712 0
396548 - disp+work.exe 9980 0
397132 - disp+work.exe 2872 0
433064 - disp+work.exe 8712 0
488716 - disp+work.exe 4772 0
507316 - disp+work.exe 7852 0
1830376 - sqlservr.exe 1812 0

507316 - disp+work.exe 7852 0
1830376 - sqlservr.exe 1812 0
=cut

__DATA__
1830376 - sqlservr.exe 1812 0
488716 - disp+work.exe 4772 0
350060 - disp+work.exe 9712 0
396548 - disp+work.exe 9980 0
327372 - disp+work.exe 7892 0
397132 - disp+work.exe 2872 0
276124 - disp+work.exe 8948 0
159176 - disp+work.exe 7292 0
283332 - disp+work.exe 9620 0
199288 - disp+work.exe 7760 0
119540 - disp+work.exe 6376 0
433064 - disp+work.exe 8712 0
255120 - disp+work.exe 4548 0
507316 - disp+work.exe 7852 0
104272 - disp+work.exe 10208 0
119728 - SavService.exe 2336 0
[download]

Update: A clarification of making the memhash....
There is kind of a duality between a hash and array. To make a hash keyed on the memory size, use split to feed pairs into %memhash.. However, keys to a hash have to be unique and I doubt that will be true in this case. I would leave this as an array as above.

#%memhash=@allprocesses; #won't work
my %memhash = map{chomp; (split(' ',$_,3))[0,2]}@array; 
#note: $array[1], the  "-" is thrown away
print Dumper \%memhash;

$VAR1 = {
          '488716' => 'disp+work.exe 4772 0',
          '119728' => 'SavService.exe 2336 0',
          '283332' => 'disp+work.exe 9620 0',
          '199288' => 'disp+work.exe 7760 0',
          '276124' => 'disp+work.exe 8948 0',
          '255120' => 'disp+work.exe 4548 0',
          '1830376' => 'sqlservr.exe 1812 0',
          '396548' => 'disp+work.exe 9980 0',
          '159176' => 'disp+work.exe 7292 0',
          '507316' => 'disp+work.exe 7852 0',
          '119540' => 'disp+work.exe 6376 0',
          '397132' => 'disp+work.exe 2872 0',
          '350060' => 'disp+work.exe 9712 0',
          '327372' => 'disp+work.exe 7892 0',
          '104272' => 'disp+work.exe 10208 0',
          '433064' => 'disp+work.exe 8712 0'
        };
[download]