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] elt = lst 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 < len(lst) and lst[start] < val: start += 1 return insert(val, lst, start)