Arrays.sort or iterative search?

I have a large integer array of mixed values I want to search for the highest and lowest values. I have a method to iterate through each element in the array. I was thinking Arrays.sort() might be faster, however I need to retain the order of the elements in the array.

Would it be more efficient to:

a) Stick with the iterative method

b) Make a copy of the array, sort and then take the first and last elements and lowest and highest respectively

Any suggestions much appreciated

Re: Arrays.sort or iterative search?

Have you heard of the QuickSelect algorithm? It's quite good at finding the min/max (I think in practice it's about O(log(n)) average, O(n) worst case).

If you only need a few min/max value, I'd say stick with the quickselect algorithm. Otherwise, it may just be better to use the full quicksort routine (which is probably the algorithm used by Array.sort()).

edit:

I was mistaken. The best way to find the #1 min/max is to iterate. The best way to find the #nth min/max is to use quickselect, or quicksort if you need to find a lot of min/max values.