# 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]
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)

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

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

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]


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)

• The parentheses around pos and item are superfluous (though arguably better for readability). – Daniel Jan 2 '18 at 12:24