Merge Factory

Instead of hardwiring lt, let's specify the comparator as a callback
(as with sort)

        sub make_merger {     
          my ($cmp) = @_;
          return sub {
            my ($s, $t) = @_;
            if (is_empty($s)) { return $t }
            if (is_empty($t)) { return $s }
            my ($sh, $th) = (head($s), head($t));
            my $dir = $cmp->($sh, $th);
            if ($dir <= 0) {
              node($sh, sub { merge(tail($s), $t      ) });
            } else {
              node($th, sub { merge($s      , tail($t)) });
            } 
          };
        }

        $merge_alphabetic = make_merger(sub { $_[0] cmp $_[1] });
        $merge_numeric    = make_merger(sub { $_[0] <=>  $_[1] });

Similarly, parametrize merge in the definition of merge_many.
More examples of function factories in the Bonus Slides