I have been trying to implement an adjacency tree sort but can't seem to get it right. The desired output would be quite like the way threads are displayed here at PerlMonks. The real data is in a MySQL database. I started out with just a "record id" and a "parent id" to connect the tree but that didn't work out. I added a "lineage" field thinking I could just sort on that but it's still not working. Here is some sample code:

#!c:\perl58\bin\perl.exe  -w
use strict;

my @array = ();

while (<DATA>)
{
    chomp($_);
    my @subarray = split(/,/,$_);
    push @array, [@subarray];
}

my @sortedarray = sort {
                        $a->[3] <=> $b->[3]
                                ||
                        $a->[4] cmp $b->[4]                        
                                ||
                        $a->[5] cmp $b->[5]
                       } @array;

for my $x(0..$#sortedarray)
{
    print "$sortedarray[$x][0] - $sortedarray[$x][6]\n";
}

#id,board,root,parent,lineage,stamp,text
__DATA__
1,2,0,0,00000000000,2006-01-02 08:15:00,test line 1 (first)
2,2,1,1,00000000001,2006-01-02 08:16:00,test line 2 (second)
3,2,1,2,00000000001-00000000002,2006-01-02 08:21:00,test line 3 (third
+)
6,2,1,1,00000000001,2006-01-02 08:23:00,test line 6 (seventh)
4,2,1,1,00000000001,2006-01-02 08:22:00,test line 4 (sixth)
7,2,1,6,00000000001-00000000006,2006-01-02 08:25:00,test line 7 (eight
+h)
5,2,1,3,00000000001-00000000002-00000000003,2006-01-02 08:23:00,test l
+ine 5 (fourth)
8,2,1,1,00000000001,2006-01-02 08:17:00,test line 8 (fifth)
[download]

And here is the output:

1 - test line 1 (first)
2 - test line 2 (second)
8 - test line 8 (fifth)
4 - test line 4 (sixth)
6 - test line 6 (seventh)
3 - test line 3 (third)
5 - test line 5 (fourth)
7 - test line 7 (eighth)
[download]

And here is what I expected to see:

1 - test line 1 (first)
2 - test line 2 (second)
3 - test line 3 (third)
5 - test line 5 (fourth)
8 - test line 8 (fifth)
4 - test line 4 (sixth)
6 - test line 6 (seventh)
7 - test line 7 (eighth)
[download]

I do not have access to any DBM::DEEP or any of the Tree modules and I can't install any either. I would love to be able to do this without a recursive subroutine but have been fighting this for two days (off and on) now and throw myself on the mercy of the Monks.