I have just tried the case where you have a lot of duplicates. For this, I have populated the array to be sorted this way (with $max being set at 4999):

$w[$_] = int rand(20) foreach (0..$max);
[download]

This is the result on two runs:

$ perl bench_sort.pl
Benchmark: timing 80 iterations of merge, quick...
     merge:  4 wallclock secs ( 3.78 usr +  0.00 sys =  3.78 CPU) @ 21
+.19/s (n=80)
     quick: 11 wallclock secs (10.70 usr +  0.00 sys = 10.70 CPU) @  7
+.48/s (n=80)

$ perl bench_sort.pl
Benchmark: timing 80 iterations of merge, quick...
     merge:  4 wallclock secs ( 3.76 usr +  0.00 sys =  3.76 CPU) @ 21
+.28/s (n=80)
     quick: 10 wallclock secs (10.65 usr +  0.00 sys = 10.65 CPU) @  7
+.51/s (n=80)
[download]

And now, the same using the following array initialization:

$w[$_] = int rand(10) foreach (0..$max);
[download]

And the results:

$ perl bench_sort.pl
Benchmark: timing 80 iterations of merge, quick...
     merge:  4 wallclock secs ( 3.76 usr +  0.00 sys =  3.76 CPU) @ 21
+.28/s (n=80)
     quick: 22 wallclock secs (22.48 usr +  0.00 sys = 22.48 CPU) @  3
+.56/s (n=80)
[download]

So, this seems to be another pathological case for quick sort, but much less significant than the two ones I previously tested.

BTW, testing this, I noticed that there was a small "off by one" mistake in the code I posted previously. To work really properly, the code needs to be changed this way:

my $max = 4999;
$w[$_] = int rand(10) foreach (0..$max);
[download]

That led to an occasional "use of uninializeds value" warning, but does not make any of the benchmark conclusions invalid.