Check if Array is Sorted

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.

Understanding the Problem

We are given an array of numbers, and we need to determine whether this array is sorted in non-decreasing order. That means each number should be less than or equal to the one that comes after it.

Let’s walk through the problem slowly, using an example and covering edge cases so even a beginner can understand what’s happening.

Example to Understand

Given Array: [1, 2, 2, 4, 5]

We start from the beginning of the array and compare each number with the next one:

• 1 ≤ 2 → okay
• 2 ≤ 2 → okay (equal is allowed)
• 2 ≤ 4 → okay
• 4 ≤ 5 → okay

Since we never found a number that is greater than the one that follows, this array is sorted.

How We Solve It Step by Step

1. Start a loop from the first element and go up to the second last.
2. At each step, compare the current number with the next one.
3. If the current number is greater than the next, return false — because the order is broken.
4. If we complete the loop without returning false, return true.

Edge Cases and Intuition

• Empty Array []: There are no elements to compare, so nothing is out of order. It is considered sorted.
• Single Element [7]: No neighbors to compare, so it's always sorted.
• Array with Duplicates [3, 3, 3]: Still sorted as long as numbers don’t decrease.
• Unsorted Case [1, 4, 2]: 4 > 2 → the order breaks → return false.

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.

Worked example

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

Compare index 0 and 1

Compare 10 and 20.

10 ≤ 20 → OK

Compare index 1 and 2

Compare 20 and 30.

20 ≤ 30 → OK

Compare index 2 and 3

Compare 30 and 40.

30 ≤ 40 → OK

Compare index 3 and 4

Compare 40 and 50.

40 ≤ 50 → OK

Final Result:

Array is sorted.

#include <stdio.h>
#include <stdbool.h>

bool isSorted(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            return false;
        }
    }
    return true;
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Is Sorted: %s\n", isSorted(arr, n) ? "true" : "false");
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

bool isSorted(const vector<int>& arr) {
    for (size_t i = 0; i < arr.size() - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            return false;
        }
    }
    return true;
}

int main() {
    vector<int> arr = {10, 20, 30, 40, 50};
    cout << "Is Sorted: " << (isSorted(arr) ? "true" : "false") << endl;
    return 0;
}

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))

public class CheckSorted {
    public static boolean isSorted(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};
        System.out.println("Is Sorted: " + isSorted(arr));
    }
}

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

// Sample Input
const arr = [10, 20, 30, 40, 50];
console.log('Is Sorted:', isSorted(arr));

package main

import (
    "fmt"
)

func isSorted(arr []int) bool {
    for i := 0; i < len(arr)-1; i++ {
        if arr[i] > arr[i+1] {
            return false
        }
    }
    return true
}

func main() {
    arr := []int{10, 20, 30, 40, 50}
    fmt.Println("Is Sorted:", isSorted(arr))
}

fn is_sorted(arr: &[i32]) -> bool {
    for i in 0..arr.len() - 1 {
        if arr[i] > arr[i + 1] {
            return false;
        }
    }
    true
}

fn main() {
    let arr = vec![10, 20, 30, 40, 50];
    println!("Is Sorted: {}", is_sorted(&arr));
}

fun isSorted(arr: List<Int>): Boolean {
    for (i in 0 until arr.size - 1) {
        if (arr[i] > arr[i + 1]) return false
    }
    return true
}

fun main() {
    val arr = listOf(10, 20, 30, 40, 50)
    println("Is Sorted: ${isSorted(arr)}")
}

func isSorted(_ arr: [Int]) -> Bool {
    for i in 0..<arr.count - 1 {
        if arr[i] > arr[i + 1] {
            return false
        }
    }
    return true
}

let arr = [10, 20, 30, 40, 50]
print("Is Sorted: \(isSorted(arr))")

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

const arr: number[] = [10, 20, 30, 40, 50];
console.log("Is Sorted:", isSorted(arr));

Time complexity

Space complexity

O(1)

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