sort_of in linear time

sort_of.py

#!/usr/bin/env python


def sort_of(numbers):
    """ Old bad code.

    Computes the minimum element of each sublist from i..n where n is the length of the list. """
    result = []
    for i in range(len(numbers)):
        sub = sorted(numbers[i:])
        result.append(sub[0])
    return result


def sort_of_linear(numbers):
    """ New linear code, relies on an inductive principle to computer the sort_of function in linear time.

    Iterating in reverse we start by saying the last element is the smallest
    element for the sublist n - 1 .. n. Then we say that given min_n represents
    the smallest element in the sublist from n - k .. n, if the n - k - 1th
    element is smaller than min_n then it is the smallest element of the sublist
    and we updated the vaule of min_n. To avoid O(n) penalty when prepending we
    append the integers instead and reverse the result at the end. Thus we get
    O(n) performance for the algorithm.

    """
    min_n = None
    res = []
    for i in range(len(numbers) - 1, -1, -1):
        if min_n is None or numbers[i] < min_n:
            min_n = numbers[i]
        res.append(min_n)
    res.reverse()
    return res


print(sort_of([2, 4, 1, 0, 3, 5]))
print(sort_of_linear([2, 4, 1, 0, 3, 5]))
# both output [0, 0, 0, 0, 3, 5].