Let me know what you guys think.

The first thing that leapt of the page for me was:

sub size(){
    # setSize()
    # Returns the number of unique elements in bag.
    my $self = shift;
    my %dictionary = %{$self->{DICTIONARY}};
    # remove empty string key created by concat operation
    #delete  $self->{DICTIONARY}{''};
    
    return scalar keys (%dictionary);
    
}
[download]

Copying an entire hash from a reference into a local hash just to return how many keys it has is insanely wasteful. Especially as you are calling this over and over again in a sort comparator.

Coded as:

sub size {
    # setSize()
    # Returns the number of unique elements in bag.
    return scalar keys %{ shift() };   
}
[download]

Will speed up your sort by orders of magnitude.

Also, you should not be using -- and would be getting a messages telling you so if you were using strict & warnings -- an empty prototype sub size() { on a subroutine that takes parameters.