gistfile1.pl

#!/usr/bin/env perl
use strict;
use warnings;
use Perl6::Say;
use Data::Dumper;
use Test::More qw(no_plan);

sub p ($) {
    say Dumper @_;
}

my $INFINITE = 100000;

sub merge {
    my @x = (@{$_[0]}, $INFINITE);
    my @y = (@{$_[1]}, $INFINITE);

    my $i = 0;
    my $j = 0;

    my $merged = [];
    while (1) {
        last if $i == @x - 1 && $j == @y - 1;
        if ($x[$i] < $y[$j]) {
            push @$merged, $x[$i];
            $i++;
        }
        elsif ($y[$j] < $x[$i]) {
            push @$merged, $y[$j];
            $j++;
        }
    }
    return $merged;
}

is_deeply( merge([2, 5, 6],          [1, 3, 4]          ) , [1, 2, 3, 4, 5 ,6]          ) ;
is_deeply( merge([2, 5, 6],          [1, 3, 4, 10, 100] ) , [1, 2, 3, 4, 5 ,6, 10, 100] ) ;
is_deeply( merge([2, 5, 6, 10, 100], [1, 3, 4]          ) , [1, 2, 3, 4, 5 ,6, 10, 100] ) ;
is_deeply( merge([2, 5, 6],          []                 ) , [2, 5, 6]                   ) ;
is_deeply( merge([],                 [1, 3, 4]          ) , [1, 3, 4]                   ) ;
is_deeply( merge([],                 []                 ) , []                          ) ;

sub merge_sort {
    my @target = @{$_[0]};
    return [$target[0]] if @target <= 1;

    my $mid = sprintf("%d", @target / 2);
    my @x = @target[0..$mid-1];
    my @y = @target[$mid..@target-1];

    return merge(merge_sort(¥@x), merge_sort(¥@y));
}

p merge_sort([4,1,2,3]);