Cacher is the code snippet organizer for pro developers

package Acme::Algorithm;
use v5.14;
our $VERSION = '0.01';
use Exporter::Auto;

sub quicksort {
    # get from  http://geekblog.oneandoneis2.org/index.php/2013/05/16/quicksort-golf
    my $array = shift;
    return [] unless (@$array);
    my $head = shift @$array;
    return [ @{ quicksort([grep { $_ <= $head } @$array])}, $head , @{ quicksort([grep { $_ > $head } @$array])}];  
   
}   

sub permutation {}

## sort
sub _merge {

    my ($left,$right) = @_;
    my @left = @$left;
    my @right = @$right;
    my @result;

    while ( @left or @right ) {
        if ( @left and @right ) {
            if ( $left[0] <= $right[0] ) {    
                push @result, $left[0];
                shift @left;
            } else {
                push @result, $right[0];
                shift @right;
            }
        } elsif ( @left ) {
                push @result, $left[0];
                shift @left;
        } elsif ( @right ) {
                push @result, $right[0];
                shift @right;
        }
    }
    @result;
}

sub merge_sort {
    my @all = @_;

    return @all if @all <= 1;

    my (@left, @right);
    my $middle = int($#all / 2);
    @left = @all[0..$middle];
    @right = @all[1 + $middle..$#all];
    
    @left = merge_sort(@left);
    @right = merge_sort(@right);

    return _merge(\@left,\@right)    
}

1;
__END__

=encoding utf-8