Off the cuff, if I am understanding you right

tie(my %cal, etc, etc, etc) or die "Cant tie cal: $!\n";
tie(my %addr, etc, etc, etc) or die "Cant tie addr: $!\n";

@sorted_cal_keys  = sort { $a <=> $b } keys %cal;
@sorted_adrr_keys = sort { $a cmp $b } keys %addr;
[download]

You didnt specify any particular relation between the 2 data sets, so there is no better way to correlate them at this point. You cant sort on both sets at the same time unless you're key's name maps to its data structure.. ala

tie(my %cal, etc) or die "cal: $!\n";
tie(my %addr, etc) or die "addr: $!\n";

$cal{"cal_$key"} = $cal_value;
$addr{"addr_$key"} = $addr_value;
# later

for ( sort { $a <=> $b || $a cmp $b } keys %cal, keys %addr) ) {
   if (m/^cal/) {           # its from the calendar
   } elseif ( m/^addr_/ ) { # from the address book
   } else {                 # where did this come from?
   }
}
[download]

use perl;