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

In reply to Re^4: Pulling an item to the front of the list by Zaxo
in thread Pulling an item to the front of the list by Tanktalus

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.