Complexity of issorted's work

Question

I doubt matlab uses this approach, but there is an efficient way to do it if you need to just keep track if an array is sorted or not. Likely, anything that can be implemented as a list should be able to use this method. It costs O(N) to build up the data structure. However, the performance (space and time) per operation is O(1 + A + C), where O(A) is the cost of the list data structure operation (include that of next and/or previous) and O(C) is the cost of the comparison operation, but it must be run before and/or after (depending on the operation) every operation that changes the list. There are a number of reasons why this approach may not be helpful or may not work (see #3).

An list (including arrays) is generally not the best choice for a data structure if you want to keep things sorted.
It's generally not useful to just know if an array is sorted or not. If you are checking if it's sorted or not, you probably intend to sort it if it's not. If this is why you want to know, see #1.
It requires ensuring that the list is not updated without following the below approach. Guaranteeing that it works for a given data type requires creating a subtype of that type that implements the approach and using the subtype instead. Otherwise, simply sorting an unsorted array will mess up the counters and require completely resetting the counters, a O(N) operation.
On the basis of point #3, such a custom subtype requires more overhead on every operation that may change the data due to needing to update the counters. The updating process requires a few comparisons and depending on the type of data being stored, those comparisons can be rather expensive..

It can be done by keeping three counters to keep track of the N-1 relationships between side-by-side elements. Those relationships can be either less than, greater than or equal to. They respectively correspond to an ordering of ascending, descending or both. When those relationships change, the counters are updated to reflect that change.

An few examples of the algorithm using an array, visual of the relationships, the counters, and what issorted should return respectively:

[1,2,3,4,5], [1<2<3<4<5], ("<" = 4, ">" = 0, "=" = 0), 1
[1,2,9,4,5], [1<2<9>4<5], ("<" = 3, ">" = 1, "=" = 0), 0
[1,2,4,4,5], [1<2<4=4<5], ("<" = 3, ">" = 0, "=" = 1), 1
[1,1,1,1,1], [1<1<1=1<1], ("<" = 0, ">" = 0, "=" = 4), 3
[9,8,7,6,4], [9>8<7>6>4], ("<" = 0, ">" = 4, "=" = 0), 2
[9,8,7,6,0], [9>8>7>6>0], ("<" = 0, ">" = 4, "=" = 0), 2
[9,6,6,6,0], [9>6=6=6>0], ("<" = 0, ">" = 2, "=" = 2), 2
[-9,-5,0,5,9], [-9<-5<0<5<9], ("<" = 0, ">" = 2, "=" = 2), 1

Where the return values mean the following:

0: Unsorted
1: Sorted in ascending order
2: Sorted in descending order
3: Sorted in both orders (empty list or all elements are equal).

Therefore, any return value greater than zero can be considered sorted one way or the other.

At the bottom, I've provided some pseudocode as to how it can be done. Since this is only guaranteed to work if a subclass of the actual data type is used, I'll just be showing what additional code would be needed to be added to each class method. To keep things short, I've only included five methods.

The constructor method to show the counters being initialized.
The update method to give an example of increasing and decreasing the counters.
The counter method which determines what counter needs to be changed.
The issorted method to determine if the list is sorted and if so in what order.
The checkstate method. This is a O(N) used to verify the state. This method that is near identical to the reset method. The reset method simply replaces every assertion in the format, "assert A == B", with an assignment in the format, "A = B". IE: "assert both == equal" becomes "both = equal". The reset method is very similar to the typical O(N) issorted function, but goes through the entire list (no early stop ) and saves the state.

A call to "super()" will designate when then the super class method should be called.

For simplicity and clarity of the code:

I have not included the code to handle errors / precision / null pointers / index at front of list / index at back of list / precision issues / ect. If the previous and/or value and/or next variables in the counter method are null, then the neither counter, a special 4th counter used in cases like this, is incremented and if that counter is more than 1 then the sort status is unsorted/unsortable/undefined and issorted returns a negative number or error. Front/back of the list just results in less comparisons being required and would make the code longer longer to add them. Precision issues would be handled the same as any other issorted method.
The constructor method has been greatly simplified as it's implementation may not be language agnostic and depends on constructor input. Therefore, it is assumed they'll be initialized as required to ensure that the counters correctly reflect the state as required.

The simplified pseudo-code should look something like this:

counter(index, add):
   next = value at the next index
   value = value at this index
   previous = value at the next index

   if previous < value:
       increment both by add
   else if previous > value:
       increment ascending by add
   else:
       increment descending by add

   if value < next:
       increment both by add
   else if value > next:
       increment ascending by add
   else:
       increment descending by add

constructor():
   ascending = initialized as required
   descending = initialized as required
   both = initialized as required

update(index):
   counter(index, -1)
   super()
   counter(index, +1)

issorted():
   % Returns 0 for unsorted, 1 for ascending order, 2 for descending order, 3 for both/empty
   % In general, array is sorted if it returns anything higher than 0.
   if ascending > 0 and descending == 0: % Ascending order if True
       return 1
   if descending > 0 and ascending == 0: % Descending order if True
       return 2
   if descending == 0 and ascending == 0: % Array is sorted in both directions
       return 3
   return 0

checkstate()
   less = new counter
   equal = new counter
   greater = new counter

   for index in indices:
        if index is not last index:
            value = value at this index
            next = value at the next index

            if value < next:
                less = less + 1
            else if value > next:
                greater = greater + 1
            else:
                next = next + 1

    assert descending == greater
    assert ascending == less
    assert both == equal