my %hash = map { substr($_, 0, 1), 1 } @original_array;
my @sorted = sort keys %hash;
[download]

Or, less explicitly and without the named temporary hash:

my @sorted = sort keys %{{map{substr($_,0,1 ),1} @original_array}};
[download]

Both methods are really the same thing; they create a hash in order to guarantee uniqueness of keys, and then use the keys to populate a new array after sorting them.