I'd be more inclined to remove the @classes array (unless it makes other things in your code more convenient) -- and push onto a departments hash to begin with. Something like:

my %departments;
while( $sth->fetchrow() ) {
    push @{$departments{$department}}, {
            class      => $class,
            department => $department,
            count      => $count,
    };
}

my @departments = map { 
        { department => $_, classes => $departments{$_} } 
} keys %departments;
[download]

You could also sort on the keys to create the final array sorted by department if desired.