how would you check if an array of integers is sorted

How would you implement a simple code to check to see if the integers in the array are already sorted or not?

I don't think I would. The check probably consumes about the same time as sort do so I would keep track of if changes has been made since last sort or not instead.

Hrm. Well you can check in O(n) time and sort in [usually] O(n log n) time. So if we checked first we'd get total complexity of:

n*log[n] + n = (n+1)*log[n] which is O(n*log[n]) except that we now handle the degenerate case of an array already being sorted, which completes in O(n).

So, for some overhead, we could get better best-case complexity and equivalent worst-case complexity.

In reality, I suspect SMA is correct; unless n is both quite large AND you're likely to get passed already-sorted arrays often.

The general algorithm to check if an array is already sorted (in ascending order) is something like:

Code:

---

foreach element in the array
    if element > nextElement
        return false immediately

//If the whole loop completes without detecting failure
return true

---