An Array Is Sorted Only When Every Adjacent Pair Agrees

Endpoints cannot prove that an array is sorted

An array is in forward order when each value is less than or equal to the value immediately after it. It is in backward order when each value is greater than or equal to the value immediately after it. For [2, 4, 4, 1], the adjacent pairs are 2, 4, then 4, 4, then 4, 1. Each pair must obey one direction. Comparing only the endpoints, 2 and 1, skips the evidence between them.

indices:  0  1  2  3
values:   2  4  4  1
pairs:      2,4  4,4  4,1

The first pair, 2 and 4, supports forward order because 2 <= 4. It does not support backward order because 2 >= 4 is false. The last pair, 4 and 1, supports backward order, but it breaks forward order. The array therefore cannot be sorted in either direction, even though its first value is greater than its last value.

Equal neighbors do not break either direction

The middle pair in [2, 4, 4, 1] is 4, 4. It satisfies 4 <= 4, so it is allowed in forward order. It also satisfies 4 >= 4, so it is allowed in backward order. Equal neighboring values do not choose a direction and do not eliminate either direction.

Sorted order allows equal values. Strictly increasing order would require every next value to be larger, and strictly decreasing order would require every next value to be smaller. This check does not require strict changes, so the repeated 4 does not make the array unsorted by itself.

Two boolean flags preserve every comparison made so far

Start both the forward flag and the backward flag as true. A flag means that every adjacent pair checked so far still supports that direction. At index 1, compare the current value 4 with the preceding value 2. Forward remains true because 2 <= 4, while backward becomes false because 2 >= 4 is false.

bool forward = true;
bool backward = true;

for (int i = 1; i < 4; i++) {
    if (arr[i - 1] > arr[i]) forward = false;
    if (arr[i - 1] < arr[i]) backward = false;
}

At index 2, compare 4 with 4. Neither flag changes because both 4 <= 4 and 4 >= 4 are true. At index 3, compare 1 with the preceding 4. Forward becomes false because 4 <= 1 is false, while backward stays false because it was already eliminated. Once a flag becomes false, a later pair cannot make the earlier contradiction disappear.

The final flag pair determines the classification

After every adjacent pair has been checked, use the flags in a fixed order. If forward is true, classify the array as forward. Otherwise, if backward is true, classify it as backward. If both are false, classify it as not at all.

The forward-first rule handles the case where every adjacent pair is equal, because both nondecreasing and nonincreasing are then true. Choosing forward first gives that case one consistent result. For [2, 4, 4, 1], the final pair is forward false and backward false, so the classification is not at all.

if (forward) {
    // classify as forward
} else if (backward) {
    // classify as backward
} else {
    // classify as not at all
}