Prove is straightforward, as you can never tell if the array is sorted without scanning each element in the array at least once.