Or even better, sort while you insert then you are guaranteed O(n) sort algorithm.

Insertion sort? Isn't that O(n**2)? There are n operations (one for each number being inserted), and for each insertion you will traverse approximately n / 2 of the numbers to find the correct insertion place, giving you n * (n / 2) = n**2 / 2 = O(n**2).

Not to mention the extra time necessary to push back the numbers into a new array when the insertion is in the middle.

Assuming the array is in random, unsorted order, the fastest way would be to traverse the array once looking for the highest and lowest values - this will be O(n) time. Any sorting will be greater than O(n).