I have been reading about arrays and I have discovered that sorted arrays seem to be faster in Java. Why is that? Does it have to do anything with the compiler or is it an efficiency of the language? Is there a circumstance when this would not be the case in Java or any other language for that matter?
There has to be some context to the statement "sorted arrays are faster in Java" that you left out.
Arrays are arrays. An array itself doesn't care in what order its elements are. Some methods, such as Arrays.binarySearch(...) require that the elements of the array are sorted, otherwise the method doesn't work correctly. But it is not the case that in general, sorted arrays are somehow always faster.
ludoviko azuaje wrote:In context, when searching for an element within an array then the array must be sorted to take advantage of binary search methods.
That is correct. But what Jesper mentioned, there is nothing special about the sorted or unsorted arrays as about the data structure as such. It is about the way you search data within an array. In your mentioned case it is binary search, which algorithm defines what kind of prerequisites needs to be satisfied in order for binary search algorithm work correctly. Read about the binary search algorithm. You'll find some useful information there.
Joseph Williamson wrote:What about branch prediction? I know that the processor will have an impact on it but can't Java the code itself help mitigate some of that time when using a sorted array?
A few responses. First, I highly doubt that a very low level pipeline optimization can have noticeable affect based on the high level organization of the data. Second, even if there is an affect, I highly doubt that the cause and effect can be conclusively established... which bring us to third, as in most cases, if you believe that there is an useful optimization, you should confirm it. Write a test program and confirm the impact. Otherwise, you are just adding complexity to your code, for something that may help, may hurt, or may have no noticeable effect on performance.