That has a problem if you generate a comparator over more than one preferred key. You're not providing for a stable comparison between two elements of the preferred list.

At best, that will lead to the sorted order depending on the unsorted order.

Maybe you're right, in theory, but my (meager) testing has shown that my algorithm works as intended, satisfying the OP.
Can you concretely demonstrate the failure mode you describe?

We're building the house of the future together.

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.

After Compline,
Zaxo