This is just a simple implementation of Patience Sorting, finding the LIS using backrefs, and doing the final merge phase to produce a sorted list. I didnt bother with anything special like binsearch or what not.

use strict;
use warnings;
use List::Util qw(shuffle);
use Text::Wrap qw(wrap);

sub patience {
    my ($deck)=@_;

    my @piles;
    CARD:
    foreach my $card (@$deck) {
        foreach my $pid ( 0..$#piles ) {
            if ( $card < $piles[$pid][-1][0] ) {
                push @{$piles[$pid]},
                        [ $card, 
                          $pid ? $piles[$pid-1][-1] : undef ];
                next CARD;
            }
        }
        push @piles,[ [ $card, 
                        @piles ? $piles[-1][-1] : undef ] ];
    }
    return \@piles
}

sub lis {
    my ($piles)= @_;
    my $iter= $piles->[-1][-1];
    my @lis;
    while ($iter) {
        push @lis, $iter->[0];
        $iter= $iter->[1];
    }
    @lis=reverse @lis;
    return \@lis
}

sub inorder {
    my ($piles)= @_;
    my @inorder=(pop(@{$piles->[0]})->[0]);
    while (@$piles) {
        my $min=0;
        foreach my $pid (0..$#$piles) {
            if (@{$piles->[$pid]} && 
                $piles->[$pid][-1][0] < $piles->[$min][-1][0]
            ){
                $min=$pid;
            }
        }
        push @inorder,(pop(@{$piles->[$min]})->[0]);
        shift @$piles while @$piles && !@{$piles->[0]};
        pop @$piles while @$piles && !@{$piles->[-1]};
    }
    return \@inorder
}

sub print_ary {
    my  ($head,$list)=@_;
    print wrap($head,"",join ", ",@$list),"\n---\n";
}


my @deck= shuffle(1..52);
my $piles=patience(\@deck);
my $lis=lis($piles);
my $inorder=inorder($piles);

print_ary("DECK   : ",\@deck);
print_ary("LIS    : ",$lis);
print_ary("INORDER: ",$inorder);
[download]

Ive been trying to put together a vEB tree implementation to play with, but so far the documentation on it that I've found hasnt been as great as it looks at first glance. Notably ive been going a little barmy working out how you update the "max" property correctly when deleting the maximum element in a tree. Probably i just tried to work on it too long and if i rereview the documentation again it will clarify itself...