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)

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