> time perl dupsort.pl u 1e6 "1e9-1-int(rand(1e9))"
999498 unique items sorted.(9)
51.254s sort, 0.891s init.
real    0m52.371s
user    0m52.059s
sys     0m0.284s
 > time perl dupsort.pl d 1e6 "1e9-1-int(rand(1e9))"
1000000 total items sorted.(9)
53.015s sort, 0.929s init.
real    0m54.151s
user    0m53.411s
sys     0m0.640s
 > time perl dupsort.pl u 1e6 "1e9-1-int(rand(1e9))"
999459 unique items sorted.(9)
51.574s sort, 0.863s init.
real    0m52.634s
user    0m52.119s
sys     0m0.480s
 > time perl dupsort.pl d 1e6 "1e9-1-int(rand(1e5))"
1000000 total items sorted.(9)
47.990s sort, 1.017s init.
real    0m49.207s
user    0m48.675s
sys     0m0.512s
 > time perl dupsort.pl u 1e6 "1e9-1-int(rand(1e5))"
99998 unique items sorted.(9)
43.938s sort, 0.938s init.
real    0m44.949s
user    0m44.639s
sys     0m0.296s
 > time perl dupsort.pl u 1e6 "1e9-1-int(rand(1e4))"
10000 unique items sorted.(9)
36.991s sort, 0.869s init.
real    0m37.921s
user    0m37.398s
sys     0m0.416s
 > time perl dupsort.pl d 1e6 "1e9-1-int(rand(1e4))"
1000000 total items sorted.(9)
47.022s sort, 0.893s init.
real    0m48.104s
user    0m47.619s
sys     0m0.464s
 > time perl dupsort.pl d 1e6 "1e9-1-int(rand(1e3))"
1000000 total items sorted.(9)
45.959s sort, 0.879s init.
real    0m47.030s
user    0m46.555s
sys     0m0.448s
 > time perl dupsort.pl u 1e6 "1e9-1-int(rand(1e3))"
1000 unique items sorted.(9)
29.405s sort, 0.876s init.
real    0m30.344s
user    0m30.106s
sys     0m0.232s
 > time perl dupsort.pl u 1e6 "1e9-1-int(rand(1e2))"
100 unique items sorted.(9)
22.611s sort, 0.909s init.
real    0m23.581s
user    0m23.201s
sys     0m0.244s
 > time perl dupsort.pl d 1e6 "1e9-1-int(rand(1e2))"
1000000 total items sorted.(9)
41.071s sort, 0.907s init.
real    0m42.182s
user    0m41.619s
sys     0m0.500s
 > time perl dupsort.pl d 1e6 "1e9-1-int(rand(1e1))"
1000000 total items sorted.(9)
39.703s sort, 0.886s init.
real    0m40.794s
user    0m39.874s
sys     0m0.524s
 > time perl dupsort.pl u 1e6 "1e9-1-int(rand(1e1))"
10 unique items sorted.(9)
15.511s sort, 0.906s init.
real    0m16.479s
user    0m16.305s
sys     0m0.160s
 > time perl dupsort.pl u 1e6 "1e9-1-int(rand(1e0))"
1 unique items sorted.(9)
10.219s sort, 0.861s init.
real    0m11.145s
user    0m10.961s
sys     0m0.180s
 > time perl dupsort.pl d 1e6 "1e9-1-int(rand(1e0))"
1000000 total items sorted.(9)
36.356s sort, 0.857s init.
real    0m37.483s
user    0m36.978s
sys     0m0.508s

##</code><code>##

uniqmergesort mergesort
52.6s (~1e6)  54.1s (1e6)
44.9s (~1e5)  49.2s
37.8s (10k)   48.1s (third line, described below)
30.3s (1k)    47.0s
23.4s (100)   42.1s
16.5s (10)    40.4s
11.1s (1)     37.5s

##</code><code>##

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

use Time::HiRes qw< time >;

sub compare {
    $_[1] cmp $_[0]
}

sub mergesort {
    my( $av )= @_;
    _mergesort( $av, 0, $#$av );
    return $av;
}

sub uniqmergesort {
    my( $av )= @_;
    $#$av -= _uniqmergesort( $av, 0, $#$av );
    return $av;
}

sub _mergesort {
    my( $av, $beg, $end )= @_;
    if(  $beg < $end-1  ) {
        my $mid= int( ($beg+$end)/2 );
        _mergesort( $av, $beg, $mid );
        _mergesort( $av, $mid+1, $end );
        merge( $av, $beg, $mid, $mid+1, $end );
    } elsif(  $beg == $end-1  ) {
        my $cmp= compare( $av->[$beg], $av->[$end] );
        if(  -1 == $cmp  ) {
            @$av[$beg,$end]= @$av[$end,$beg];
        }
    }
}

sub _uniqmergesort {
    my( $av, $beg, $end )= @_;
    if(  $beg < $end-1  ) {
        my $mid= int( ($beg+$end)/2 );
        my $d1= _uniqmergesort( $av, $beg, $mid );
        my $d2= _uniqmergesort( $av, $mid+1, $end );
        $d1 += uniqmerge( $av, $beg, $mid-$d1, $mid+1, $end-$d2 );
        return $d1+$d2;
    }
    if(  $beg == $end-1  ) {
        my $cmp= compare( $av->[$beg], $av->[$end] );
        if(  -1 == $cmp  ) {
            @$av[$beg,$end]= @$av[$end,$beg];
            return 0;
        }
        return 1  if  0 == $cmp;
    }
    return 0;
}

sub merge {
    my( $av, $a, $b, $c, $d )= @_;
    my $beg= $a;
    my @i;
    while(  $a <= $b  &&  $c <= $d  ) {
        my $cmp= compare( $av->[$a], $av->[$c] );
        push @i, $a++
            if  -1 != $cmp;
        push @i, $c++
            if  1 != $cmp;
    }
    @$av[$beg..$d]= @$av[ @i, $a..$b, $c..$d ];
}

sub uniqmerge {
    my( $av, $a, $b, $c, $d )= @_;
    my $beg= $a;
    my $end= $d;
    my @i;
    while(  $a <= $b  &&  $c <= $d  ) {
        my $cmp= compare( $av->[$a], $av->[$c] );
        push @i, $a++
            if  -1 != $cmp;
        push @i, $c++
            if  -1 == $cmp;
        $c++, $end--
            if  0 == $cmp;
    }
    @$av[$beg..$end]= @$av[ @i, $a..$b, $c..$d ];
    return $d-$end;
}

if(  3 != @ARGV  ||  $ARGV[0] !~ /^[ud]$/  ) {
    print join ' ', @{mergesort([@ARGV])};
    print join ' ', @{uniqmergesort([@ARGV])};
} else {
    my $t= time();
    my( $u, $n, $e )= @ARGV;
    my $s= eval "package x; no strict; sub { $e }"
        or  die "Can't compile ($e): $@\n";
    my @l;
    $#l= $n-1;
    @l= ();
    push @l, $s->()
        for  1..$n;
    my $m= time();
    if(  'u' eq $u  ) {
        uniqmergesort( \@l );
        print 0+@l, " unique items sorted.(", length($l[0]), ")";
    } else {
        mergesort( \@l );
        print 0+@l, " total items sorted.(", length($l[0]), ")";
    }
    my $e= time();
    printf "%.3fs sort, %.3fs init.\n", $e-$m, $m-$t;
}