Recursive sorting algorithm

Question

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

• QuIcKmAtHs: If I am not wrong that is insertion sort, which runs at $O(n^2)$ in worst case scenario.
• Snowbody: @XCoderX you need to backslash the dollar signs here to get mathjax. e.g. \$O(n^2)\$ is written \\$O(n^2)\\$

Answer 1

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 >= 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) \$.

Answer 2

I have a few suggestions for improving your code.

• Good job using docstrings. Perhaps you should mention what the parameters actually represent, e.g. lst represents the list to be sorted.

• if lst == []:
   return []
  if len(lst) == 1:
   return [lst[0]]
  

  This could be replaced by:

  if len(lst) <= 1:
   return lst[:]
  

  The [:] is slice notation for a copy of the entire list.

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

  Since lst is already guaranteed to be a copy here, no need to make four new lists. Just insert the item into the existing lst and return it, e.g.

  lst.insert(i, val)
  return lst
  

• 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
  

  It is not Pythonic to increment your own index to iterate over a list. Instead you should use the builtin enumerate:

  for (pos, item) in enumerate(lst):
   if item >= val:
   return insert(val, lst, pos)
  # if not found
  lst.append(item)
  return lst
  

• Daniel: The parentheses around pos and item are superfluous (though arguably better for readability).