If the order in which you are populating the array is important, then populate both an array and an %already_seen hash (don't populate the array if the element exists in the hash). This will be much faster than greping your array each time.
If the order of insertion is not important, then don't use an array, use only a hash, you are guaranteed against duplicates. You can still sort your hash on keys.
Well, if the order is important, you might still use only a hash, with the elements as keys, and the order of insertion as values. At then end, you only need to sort the hash on the values. This will probably not be faster than populating both an array and a hash, but if speed is not crucial (no huge data set), the code will be a bit simpler.