Given the (very strict) restrictions (proper subset, sorted) , my solution would be:

sub pjotrik {
    my ($a, $b) = @_;
    my $i = 0;
    return [ map { if ($i < @$b && $_ == $$b[$i]) { $i++; () } else { 
+$_ } } @$a ];
}
[download]

But the use of == makes it somewhat vulnerable. ~~ should improve that, but I have no experience with it.

UPDATE: Note that as well as ikegami's solution, this is based on the idea of merging.