Recursive sorting algorithm I wrote a recursive sorting algorithm and was wondering what would be the run time complexity of this. The bulk of the work is done in the push_up function, which I think is linear in time. There are a linear amount of recursive calls though. If \$n\$ is the length of the list, would the runtime then be \$O(n^2)\$?

def sort(lst):
    """Recursive sorting algorithm. Sorts the remainder of the list 
    and then pushes the first element up to its appropriate position"""

   if lst == []:
       return []
   if len(lst) == 1:
       return [lst[0]]
   elt = lst[0]
   sorted_lst = sort(lst[1:])
   return push_up(elt, sorted_lst)

def insert(val, lst, i):
    """Inserts [val] into [lst] at index [i] """

    return lst[:i] + [val] + lst[i:]

def push_up(val, lst):
    """Pushes [val] up the list until it reaches its sorted position.
    Precondition: lst is sorted"""
    start = 0
    while start &lt; len(lst) and lst[start] &lt; val:
        start += 1

    return insert(val, lst, start)
Yes.

You can see that your sort function operates by recursing directly on itself, using a shorter-by-one version of its list parameter. This is stopped when the list is of length 0 or 1. (That code should be cleaned up.) So your sort recurses n-1 times, given n &gt;= 2.

Each time it recurses, sort calls push_up once. The push_up function linearly scans the list, which is of length 1, then 2, then ... n-1.

So in the worst case (input array is reverse-sorted) you have scans of total length \$ \sum 1 ... (n-1) \$, which makes your code \$ O(n^2) \$.