How to check if the elements of an array are in sorted order

Problem statement

Given an array, check whether the elements of the array are in sorted order.

Assume that the sorted order is ascending in nature.

If the array is sorted, then print Array is sorted.
If the array is not sorted, then print Array is not sorted.

Examples

array - [1,2,3,4]
- The output should be Array is sorted as the elements are in sorted order.
array - [1,4,5,4]
- The output should be Array is not sorted as the elements are not in sorted order.

Algorithm

This problem can be solved in two ways.

Recursive approach
Iterative approach

Recursive approach

The base case for this approach is when there is zero or one element left for comparison.

The steps in this approach are as follows.

Return true when the size of the array becomes zero or one.
Check the last two elements of the array.

a. If the last two elements are sorted, perform a recursive call with the previous element, i.e., n-1.

b. If it returns false, that indicates the array is not sorted.
The recursion will eventually fall to step 1 when all the array elements are in sorted order.

Time Complexity - O(n)
Space Complexity - O(n) (Considering the recursive call stack)

import java.util.Arrays;
public class Main {
    private static boolean isSortedArray(int[] array, int n){
        if(n == 1 || n == 0) return true;
        return array[n-2] <= array[n-1] && isSortedArray(array, n-1);
    }
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        System.out.println("The array " + Arrays.toString(arr) + " " + (isSortedArray(arr, arr.length)?"is":"is not") + " sorted.");
        System.out.println("--------");
        arr = new int[]{1,3,2,4,5};
        System.out.println("The array " + Arrays.toString(arr) + " " + (isSortedArray(arr, arr.length)?"is":"is not") + " sorted.");
    }
}

Iterative approach

The steps in the iterative approach are as follows.

If the length of the array is zero or one, then the array is sorted.
Start looping from the first element.
Compare every two elements.

a. If the two elements are sorted, move to the next element, i.e., i+1.

b. Otherwise it will return false, which indicates that the array is not sorted.
The loop will eventually come to the end of the array when all the array elements are in sorted order.

Time Complexity - O(n)
Space Complexity - O(1)

import java.util.Arrays;
public class Main {
    private static boolean isSortedArray(int[] array, int n){
        if(n == 1 || n == 0) return true;
        for(int i = 1; i < n; i++){
            if(array[i] < array[i-1] ) return false;
        }
        return true;
    }
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        System.out.println("The array " + Arrays.toString(arr) + " " + (isSortedArray(arr, arr.length)?"is":"is not") + " sorted.");
        System.out.println("--------");
        arr = new int[]{1,3,2,4,5};
        System.out.println("The array " + Arrays.toString(arr) + " " + (isSortedArray(arr, arr.length)?"is":"is not") + " sorted.");
    }
}

How to check if the elements of an array are in sorted order

Problem statement

Examples

Algorithm

Recursive approach

The recursive approach in action

Code

Example 1

Iterative approach

The iterative approach in action

Example 2