my $testarray = [
                 { messageId => 1,
                   parent    => 1 },
                 { messageId => 2,
                   parent    => 1 },
                 { messageId => 3,
                   parent    => 1 },
                 { messageId => 4,
                   parent    => 2 },
                 { messageId => 5,
                   parent    => 3 },
                 { messageId => 6,
                   parent    => 2 },
                 { messageId => 7,
                   parent    => 4 }
                 ];
                 


#wander down array, setting "children" field

foreach my $key (@$testarray) {
   
   next if ($key->{parent} eq $key->{messageId}); # skip root nodes
   push @{$$testarray[$key->{parent} - 1]->{children}}, $key->{messageId};
   # messageIds are 1-relative, arrays are 0-relative
}   


# build up a sorted array of elements...

my @newstack;

# a. retrieve each element in turn
foreach my $message (@$testarray) {
# b. if parent = messageid, push onto new stack, and go back to the beginning
  if ($message->{parent} eq $message->{messageId}) {
     push @newstack,$message;
     next;
  }
  # c. insert it into the new stack, just after the parent
  for (my $loop = scalar(@newstack) - 1;$loop >= 0;$loop--) {
     #d. if the last element IS the parent, just push it and move on
     if ($newstack[$loop]->{messageId} eq $message->{parent}) {
        push @newstack,$message;
        $loop = -1;
        next;
     }
     #e. move the stack down a place
     $newstack[$loop + 1] = $newstack[$loop];
     #f. insert new value, if appropriate and trip out of loop
     if ($newstack[$loop - 1]->{messageId} == $message->{parent}) {
        $newstack[$loop] = $message;
        $loop = -1;
     }
  }
}
#print the results
print "Message\tParent\n";
print  $_->{messageId} . "\t" . $_->{parent} . "\n" for @newstack;