06. Check Whether an Array Is Sorted

Difficulty:EasyPattern:Linear ScanTime:O(n)Space:O(1)

Verify if an array's elements are ordered in non-decreasing sequence ($arr[i] \le arr[i+1]$).

How It Works & Algorithmic Design

This uses an Adjacent Pair Comparison strategy with Early Termination:

Invariant: An array is sorted if every consecutive pair satisfied $arr[i - 1] \le arr[i]$.
Iteration: Start looping from index 1 up to arr.length - 1.
Violation Check: Compare arr[i] against its preceding neighbor arr[i - 1]. If arr[i] < arr[i - 1], a sorting violation has occurred. Instantly return false.
Success Return: If the loop finishes without finding any out-of-order pair, return true.

Why This Approach Works Best

It avoids checking $O(n^2)$ pairs by relying on transitivity: if $a \le b$ and $b \le c$, then $a \le c$. Comparing adjacent items in a single pass ($O(n)$ time, $O(1)$ space) is sufficient.

Example Walkthrough 1 (Sorted)

Input: [2, 5, 8, 8, 12]

Non-decreasing array containing a duplicate.

Comparisons: 5 >= 2 (OK) -> 8 >= 5 (OK) -> 8 >= 8 (OK) -> 12 >= 8 (OK)

No violation found.

Output: true

Array is sorted.

Example Walkthrough 2 (Unsorted)

Input: [1, 3, 2, 4]

Unsorted array.

Comparisons: 3 >= 1 (OK) -> 2 < 3 (VIOLATION!)

Returns false immediately at index 2.

Output: false

Array is not sorted.

Answer: Check array order

function isSorted(arr) {
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < arr[i - 1]) return false;
  }
  return true;
}

💡 Scan adjacent elements and return false upon detecting any out-of-order pair.

Key Takeaways

Transitivity property allows order verification through adjacent comparisons alone.
Early return optimizes average runtime when input arrays are unsorted.
Single-pass linear scan yields optimal $O(n)$ time performance.