Both these are along the lines of what I was thinking of when I posted, but couldn't wrap my brain around the implementation.

Per your /msg, I agree that as the individual arrays are already sorted, there is no need for the binary search, and so a merge algorithm with a small buffer can step through the arrays picking out the next highest value and tracking where it's got to in each array. In theory, this can be extended to handle any number of arrays, though this isn't (currently) a requirement, but my code below does do that.

It struck me that this is probably an algorithm to which tye's Algorithm::Loops::loops code would lend itself, and I was hoping that someone who groks that, (which still defeats me for some reason?), would post some code. I understand your frustration at your current Perless state.

The problem I had with implementing it revolved around how to detect the end of the main loop. Ie. How to detect when the indexes into the individual arrays had reached the end--across all of the arrays. I eventually came up with a grep in a scalar context solution that works, but I'm still not sure that there isn't a better way? I keep thinking about initialising the array indexes to $#array and stepping them backwards, so that I can use their transition to zero to detect the ends...

Anyway, this is what I came up with so far. I'm not sure how it compares efficiency-wise with the sort them all together solutions, but it does avoid the need for a large AoA or AoCompositeTags. In theory it's O(n), but as we have both meditated on in the past, O(n) Perl code isn't necessarially quicker than O(n log n) C-via-builtins code.

The tricky bits are:

1. how to handle min to return the indexes whilst also handling running off the end of the arrays

   (the reduce line).

2. the nested indexing in the push line.

   Trying to handle that in C code is giving me nightmares :) I do love Perl.

Update: Added fixes 1 & 2 found by Not a Number++ below

#! perl -slw
use strict;
use Data::Dumper;
use List::Util qw[ reduce ];

use constant MAXINT => 2**32;

sub seq {
    my $aoa = shift;
    my @is = ( 0 ) x @$aoa;
    my @seqs;
    my @seq;

sub seq {
    my $aoa = shift;
    my @is = ( 0 ) x @$aoa;
    my @seqs;
    my @seq;

    while( grep{ $is[ $_ ] < @{ $aoa->[ $_ ] } } 0 .. $#is ) {
#        print "\n@is";
#        print "@$_" for @seq;
        my $iLow  = reduce {
            ( $aoa->[ $a ][ $is[ $a ] ] || MAXINT )
            <
            ( $aoa->[ $b ][ $is[ $b ] ] || MAXINT )
            ? $a : $b
        } 0 .. $#is;

        push @seq, [ $aoa->[ $iLow ][ $is[ $iLow ] ], $iLow, $is[ $iLo
+w ] ];
        ++$is[ $iLow ];

        if( @seq > 1 and $seq[ -1 ][ 0 ] > ( $seq[ -2 ][ 0 ] + 1 ) ) {
            my $temp = pop @seq;                       ## Fix 1a
            push @seqs, [ @seq ] if @seq >= 4;
            @seq = $temp;                              ## Fix 1b
        }
    }
    push @seqs, \@seq if @seq >= 4;                    ## Fix 2
    return @seqs;
}

my @data = (
    [ 100, 204, 312 ],
    [ 102, 313, 409 ],
    [ 205, 206, 315 ],
    [ 207, 210, 314 ],
);

my @seqs = seq( \@data );

print map{
    sprintf "Value: %d at array:%d position:%d\n", @$_
} @$_ for @seqs;

__END__
c:\test>588553
Value: 204 at array:0 position:1
Value: 205 at array:2 position:0
Value: 206 at array:2 position:1
Value: 207 at array:3 position:0

Value: 312 at array:0 position:2
Value: 313 at array:1 position:1
Value: 314 at array:3 position:2
Value: 315 at array:2 position:2
[download]