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];
        }
    }
}

##</code><code>##

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;
    #^^^^^^^^
}

##</code><code>##

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;
}

##</code><code>##

(...done...)= items already sorted and (less dups) output
p= the pivot or a duplicate of it
b= "before", things known to be "less than" the pivot
a= "after", things known to be "greater than" the pivot
u= unsorted items (but fit within the current partition)
n= next item to compare to our pivot
(...to-do...)= the partitions to sort after we output this one

(...done...) b b b b b u u u u u n p a a a a a p p p (...to-do...)
if n is a  "b", swap:  b<------->u
if n is an "a", swap:            p-a
if n is a  "p", swap:            p a<------->p

##</code><code>##

(...done...) b b b b b b b b p a a a a a a a p p p p (...to-do...)
            |---sort next---|

##</code><code>##

(...done...) b p a p p (...to-do...)
            |write|