is_sorted.py

# check if an array is monotonically increasing
# with recursion

def is_sorted(A):
    n = len(A)
    if n <= 1:
        # arrays of no elements or one element are always sorted
        return True

    first_half = A[:n//2]
    second_half = A[n//2:]

    # check that the first half is sorted,
    # and the second half is sorted,
    # and if so, that the largest number in the first half
    # is less than the smallest number in the second half.
    if (is_sorted(first_half) and
        is_sorted(second_half) and
        first_half[-1] <= second_half[0]):
            return True

    # if none of the above, it's not sorted.
    return False

def is_sorted_cam(A):
    n = len(A)
    if n <= 1:
        return True

    if is_sorted_cam(A[:n-1]) and A[n-2] <= A[n-1]:
        return True

    return False

"""
Both of these functions are actually special cases of the same algorithm!
Consider this algorithm:

    is_sorted(A):
        if A has 1 or fewer elements, it is sorted
        split A in two along some partition
        check that the first partition is sorted
        check that the second partition is sorted
        check that the boundary between them is increasing
        if all three cases hold, it is sorted, else false

My example chooses the partitions as 0 through n/2-1 and n/2 through n-1.
Your example chooses the partition 0 through n-2, and a second partition with
just one element. The one element partition implicitly must be sorted and so
you get to omit the recursive call! But we could add it back and check if that
one element is sorted, and it would still be correct.

Both versions are correct and have runtimes of the same order.
"""

# Functional programming also gives us a perverse way to compute this without loops.
foldl = lambda f, a, l: a if len(l) == 0 else foldl(f, f(a, l[0]), l[1:])
is_sorted_functional = lambda a: foldl(lambda a, x: (a[0] and a[1] <= x, x), (True, float('-inf')), a)[0]

if __name__ == '__main__':
    for test in [
            [],
            [1],
            [1,2,3],
            [1,3,2],
            [5,1,2,3],
            [1,2,3,0],
            [1,2,3,4,5,6,7,8,9,10],
            [1,5,1,2,5,1,4],
            [5,5,5],
            ]:
        result = is_sorted(test)
        print(result, test)