This is a FAQ. See perlfaq4: How do I sort a hash?. This is also available locally to you by typing perldoc -q sort in your command prompt.

Why don't you store the values individually as keys, and format them directly when printing?

I think of a structure ordered by "logical size" of each value:

%Date_Time = (
  Year => {
    Month => {
      Day => {
        Hour => {
          Minute => {
            Second => 1,
          },
        },
      },
    },
  },
);

for my $year ( sort keys %Date_Time ) {

  for my $month ( sort keys %{ $Date_Time{$year} } ) {

    for my $day ( sort keys %{ $Date_Time{$year}->{$month} } ) {

      my $time_r = $Date_Time{$year}->{$month}->{$day};

      for my $hour ( sort keys %$time_r ) {

        for my $minute ( sort keys %{ $time_r->{$hour} } ) {

          for my $second ( sort keys %{ $time_r->{$hour}->{$minute} } 
+) {

            printf "Date: %d-%d-%d %02d:%02d:%02d\n",
             $day, $month, $year, $hour, $minute, $second;
         }
      }
    }
  }
}
[download]

You appear to want to sort into conventional time order, but your date string will sort by day number, then by month and then by year -- which is backwards... Then you are sorting by seconds, then minutes and then hours -- also backwards. Or is that really what you want ?

The problem appears to be in two parts: (a) construct something that will sort into the order you want, (b) map that back to your actual keys. Perhaps:

use strict ;
use warnings ;

my %Date_Time = (
  '03-12-2008' => { '0'  => { '8'  => { '5'  => 'a',
                                        '15' => 'b', },
                              '08' => { '22' => 'c',
                                        '05' => 'd', }, }, },
  '04-12-2008' => { '0'  => { '5'  => { '8'  => 'e', }, }, },
  '05-12-2008' => { '0'  => { '5'  => { '9'  => 'f', }, }, },
) ;

my @order ;
foreach my $date (keys %Date_Time) {
  my ($d, $m, $y) = split(/-/, $date) ;
  my $o = sprintf("%04d%02d%02d", $y, $m, $d) ;
  foreach my $sec (keys %{$Date_Time{$date}}) {
    foreach my $min (keys %{$Date_Time{$date}{$sec}}) {
      foreach my $hour (keys %{$Date_Time{$date}{$sec}{$min}}) {      
+   
        push @order, $o . sprintf("%02d%02d%02d", $hour, $min, $sec)
                        . ":$date:$hour:$min:$sec" ;      
      } ;
    } ;
  } ;
} ;

@order = sort @order ;

foreach my $o (@order) {
  my (undef, $date, $hour, $min, $sec) = split(/:/, $o) ;
  print "Date=>$date $hour:$min:$sec = ", $Date_Time{$date}{$sec}{$min
+}{$hour}, "\n" ; 
} ;
[download]

Your program works exactly as expected, I didn't change anything except for the initalization to test your code:

#!/usr/bin/perl
use warnings;
use strict;

my %Date_Time = (
 "05-12-2008" =>{ 0  => { 5 => {9 => 1}}} ,   
 "03-12-2008" =>{ 2  => { 8 => {5 => 1}}} ,   
 "04-12-2008" =>{ 0  => { 5 => {8 => 1}}} 
);   

#$dateOut = "$oDay".'-'."$oMon".'-'."$oYear";
#print"Date out => $dateOut\n";                            
#$Date_Time{$dateOut}{$dSec}{$dMin}{$dHour} = 1;

#Retrieving the hash array output
foreach my $date ( sort keys %Date_Time ) {
        #print"Date=> $date\n";
        foreach my $sec (sort keys %{$Date_Time{$date}}) {
            #print"Seconds=> $sec\n";
            foreach my $minute (sort keys %{$Date_Time{$date}{$sec}}) 
+{
                #print"Minute=> $minute\n";
                foreach my $ hour (sort keys %{$Date_Time{$date}{$sec}
+{$minute}}) {            

                    print"Date=>[$date] --> [$hour]:[$minute]:[$sec]\n
+";
                    

                }
            }
        }
    }

output:
Date=>[03-12-2008] --> [5]:[8]:[2]
Date=>[04-12-2008] --> [8]:[5]:[0]
Date=>[05-12-2008] --> [9]:[5]:[0]
[download]