#!/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;
}