Well, the code being measured does one pass through the array. Sorting can in general not be done in linear time, so asymptotically you won't gain anything by sorting first.
Well sure, but from an asymptotic approach both unsorted and sorted are "linear", so asymptotics don't necessarily provide enough information to answer GP's question.