Check if Array is Sorted using Loop - Optimal Algorithm

Contents

ProblemExamplesVisualizationSolutionAlgorithmCodeTimeSpace Detailed Exmpl

Problem Statement❯

Given an array of integers, determine whether the array is sorted in strictly non-decreasing (ascending) order.

  • An array is considered sorted if for every index i, the condition arr[i] ≤ arr[i+1] holds.
  • If the array is empty or contains only one element, it is considered sorted.

Return true if the array is sorted, otherwise return false.

Examples❯

Input Array Is Sorted? Description
[1, 2, 3, 4, 5] true Strictly increasing orderVisualization
[1, 2, 2, 3, 4] true Non-decreasing (duplicates allowed)Visualization
[5, 4, 3, 2, 1] false Strictly decreasing<Visualization/td>
[10, 20, 15, 25] false Disorder between 20 and 15Visualization
[100] true Single-element array is always sortedVisualization
[] true Empty array is trivially sortedVisualization
[1, 3, 5, 7, 6] false Sorted until the last element breaks the orderVisualization
[1, 2, 3, 3, 3] true Flat segments are allowed in non-decreasing orderVisualization

Visualization Player

Solution❯

To determine if an array is sorted, we check whether each element is less than or equal to the one that comes after it. This is because in a non-decreasing (ascending) order, every element should be ≤ the next one.

What Happens in Different Cases?

  • Fully Sorted Array: If the elements go up or stay the same from left to right (like [1, 2, 2, 3, 5]), then it is sorted.
  • Unsorted Array: If there’s any element that is greater than the one after it (like [3, 5, 4]), the order is broken, and we return false.
  • Array with Duplicates: Duplicates do not break the sorting as long as the order doesn't decrease (e.g., [1, 1, 2, 2] is sorted).
  • Single-Element Array: A single number is always considered sorted since there are no comparisons to make.
  • Empty Array: An empty list has no elements out of order. So by definition, it is sorted.

This solution works by simply looping once through the array and checking every pair of neighboring elements. If we ever find a case where a number is greater than the one after it, we know the array is not sorted and can return false immediately. If we reach the end without such a case, the array is sorted.

Why This Works Efficiently

We only look at each element once, so the entire process takes O(n) time where n is the size of the array. This is the most optimal way to check for sorting.

Algorithm Steps❯

  1. Given an array arr.
  2. Iterate through the array from index 0 to n - 2.
  3. For each index i, check if arr[i] > arr[i + 1].
  4. If the condition is true, return false (array is not sorted).
  5. If the loop completes without finding any such case, return true.

Code

Python
JavaScript
Java
C++
C
def is_sorted(arr):
    for i in range(len(arr) - 1):
        if arr[i] > arr[i + 1]:
            return False
    return True

# Sample Input
arr = [10, 20, 30, 40, 50]
print("Is Sorted:", is_sorted(arr))

Time Complexity

CaseTime ComplexityExplanation
Best CaseO(1)If the array is not sorted and the first pair is unsorted, the algorithm returns immediately.
Average CaseO(n)The loop may check several elements before detecting disorder in a random unsorted array.
Worst CaseO(n)If the array is fully sorted, the algorithm needs to scan all elements from index 0 to n - 2.

Space Complexity

O(1)

Explanation: The algorithm uses only constant space for the loop counter and comparisons, without any additional data structures.

Detailed Step by Step Example❯

Let's check if the following array is sorted in ascending order.

{ "array": [10,20,30,40,50], "showIndices": true }

Compare index 0 and 1

Compare 10 and 20.

10 ≤ 20 → OK

{ "array": [10,20,30,40,50], "showIndices": true, "highlightIndices": [0,1], "labels": {"0":"i","1":"i+1"} }

Compare index 1 and 2

Compare 20 and 30.

20 ≤ 30 → OK

{ "array": [10,20,30,40,50], "showIndices": true, "highlightIndices": [1,2], "labels": {"1":"i","2":"i+1"} }

Compare index 2 and 3

Compare 30 and 40.

30 ≤ 40 → OK

{ "array": [10,20,30,40,50], "showIndices": true, "highlightIndices": [2,3], "labels": {"2":"i","3":"i+1"} }

Compare index 3 and 4

Compare 40 and 50.

40 ≤ 50 → OK

{ "array": [10,20,30,40,50], "showIndices": true, "highlightIndices": [3,4], "labels": {"3":"i","4":"i+1"} }

Final Result:

Array is sorted.