Best search performance could be reached as O(log(N)) by using balanced tree.
in reply to A short meditation about hash search performance
You could implement this as a perl module, although this will be much slower than internal implementation O(N).
Also do not forget that adding into search list also counts, and I think adding into a hash would cost O(1)
It is know that commonly used in C library qsort is also O(N*N) in worst case and something like O(N*LOG(N)) in real life.
Also sorting method changed to mergesort in perl-5.8.0 and it was qsort for earlier perls.
Courage, the Cowardly Dog