Kappa's Lair v5

Вдогонку к http://friendfeed.com/kkapp/b5d3658c.

Вымучивал полчаса. +Пессимизация по памяти.

#! /usr/bin/perl
use strict;
use warnings;

use Test::Most;
use Data::Dump;

sub msort {
	my @arr = @_;

	if (@arr <= 1) {
		return @arr;
	}

	my $mid = int ($#arr / 2);
	my @left = msort(@arr[0 .. $mid]);
	my @right = msort(@arr[$mid + 1 .. $#arr]);

	my ($li, $ri, @new_arr) = (0, 0);

	while ($li <= $#left || $ri <= $#right) {
		if	($li > $#left) {
			push @new_arr, $right[$ri++];
		}
		elsif	($ri > $#right) {
			push @new_arr, $left[$li++];
		}
		elsif	($right[$ri] < $left[$li]) {
			push @new_arr, $right[$ri++];
		}
		elsif	($left[$li] <= $right[$ri]) {
			push @new_arr, $left[$li++];
		}
		else {
			die "Should not happen";
		}
	}

	return @new_arr;
}

cmp_deeply([msort(1)], [1]);
cmp_deeply([msort(1, 2)], [1, 2]);
cmp_deeply([msort(0, 2)], [0, 2]);
cmp_deeply([msort(0, 1, 2)], [0, 1, 2]);
cmp_deeply([msort(1, 1, 2)], [1, 1, 2]);
cmp_deeply([msort(2, 1, 0)], [0, 1, 2]);
cmp_deeply([msort(1, 0)], [0, 1]);
cmp_deeply([msort(1, 1, 1, 0, 0, 1, 0)], [0, 0, 0, 1, 1, 1, 1]);
cmp_deeply([msort(9, 8, 7, 6, 5, 2, 1)], [1, 2, 5, 6, 7, 8, 9]);
cmp_deeply([msort()], []);
done_testing;