I was surprised to find that you're right. My own meager tests confirm that your algo acts stable 10000 times out of 10000 under both mergesort and quicksort.

I wrote a comparator I called stable which maintains the given order for the preferred keys. For 10000 cycles this little program shuffles a list and sorts the result with both preferred and stable. The sorted lists are compared and they're printed if the results differ.

#!/usr/bin/perl

use sort '_quicksort';
use List::Util 'shuffle';

my @items = 'A'..'X';

my $prefer = prefer(qw/G B Z I Q J/);
my $stable = stable(qw/G B Z I Q J/);

for (1..10000) {
    my @foo = shuffle @items;
    my $p = "@{[sort {&$prefer} @foo]}\n";
    my $s = "@{[sort {&$stable} @foo]}\n";
    print "@foo\n", $p, $s if $p ne $s; 
}

sub prefer {
    my @preferred = @_;
    sub {
        for ( @preferred ) {
            $a eq $_ and return -1;
            $b eq $_ and return  1;
        }
        $a cmp $b
    }
}

sub stable {
    my %preferred;
    @preferred{@_} = 0 .. $#_;
    sub {
        exists $preferred{$a} and exists $preferred{$b}
            and return $preferred{$a} - $preferred{$b};
        exists $preferred{$a} and return -1;
        exists $preferred{$b} and return  1;
        $a cmp $b;
    }
}
[download]

I got no disagreements between the two, with either mergesort or quicksort. That wasn't what I expected. I'd love to know why yours works so well.

I'm a great believer in theory. When a theory fails comes the most interesting times.