Using Sort::Key:

(Note that this code really does a natural sort inside the path parts so, for instance, "a2" goes before "a12")

use Sort::Key::Natural qw(mkkey_natural);
use Sort::Key qw(keysort);

my @arr = (
  { 'path' => '/c/', dir => '/' },
  { 'path' => '/c/a1.mp3', 'file' => 1, 'dir' => '/c' },
  { 'path' => '/c/a2.mp3', 'file' => 1, 'dir' => '/c' },
  { 'path' => '/c/bb/aa1.mp3', 'file' => 1, 'dir' => '/c' },
  { 'path' => '/c/bb/aa2.mp3', 'file' => 1, 'dir' => '/c' },
  { 'path' => '/c/bb/aa12.mp3', 'file' => 1, 'dir' => '/c' },
  { 'path' => '/c/bb/', 'dir' => '/c' },
  { 'path' => '/c/cc/', 'dir' => '/c' },
  { 'path' => '/c/aa/', 'dir' => '/c' }
);

sub mkkey_fspath {
    my $path = shift;
    join("\x00/", map(mkkey_natural($_), split(/\/+/, $path)))
}

my @arr = keysort {
    if ($_->{file}) {
        my ($dir, $file) = $_->{path} =~ m|^((?:.*/)?)([^/]*$)|;
        join("\x01/", mkkey_fspath($dir), mkkey_fspath($file));
    }
    else {
        my $dir = $_->{path};
        $dir =~ s|/+$||;
        mkkey_fspath($dir);
    }
} @arr;

foreach (@arr) {
    my %h = %{$_};
    print $h{'path'}."\n";
}
[download]

update: as diweooy pointed out there was an error on the key generation sub.