Insertion sort via recursion I'm learning about algorithms and have been recently experimenting with insertion sort via recursion in Python. 

My code works fine, but I was wondering if there are any possible improvements that can be made. I am especially interested in ways to reduce the actual content of the code (i.e. make it shorter) or improve the speed.

def insertionsort(alist):
    i = len(alist)
    if i &gt; 2:
        temp = alist[:i-1]
        insertionsort(temp)
        alist[:i-1] = temp[:i-1]

    k = len(alist) - 1
    m = len(alist)

    while k &gt;= 1 and alist[k-1] &gt; alist[k]:
        front = alist[k]
        back = alist[k - 1]
        alist[k] = back
        alist[k-1] = front

        k = k - 1


A = [4, 1, 6, 3, 9, 10]
insertionsort(A)

print(A)
Starting with the low-hanging fruit: A variable called 'temp' is a big sign that you can do better. If you were to set up your code so that it returned a new list rather than modifying it in place, you could do this:

alist[:i-1] = insertionsort(alist[:i-1])


The rest of your code assumes that we will be working on the original, but the easiest fix for that is to make a copy at the earliest opportunity. If you do that early (and with an appropriate comment), and you don't need the original list anymore (you don't), then you can reuse the name alist without losing clarity. Unfortunately, copying the list is bad for performance, but readability needs to come first. But way down the bottom, I will point out a bigger improvement that will mean we don't actually have to choose between performance and readability here. 



You can also eliminate that i: Python allows negative indices to all builtin sequences, which are defined to count from the back. So the above line is just:

alist[:-1] = insertionsort(alist[:-1])


and the condition above it can test against len(alist) explicitly.



In your second loop, you use four lines to swap two list elements. This can be more idiomatically done in one line using tuple assignment:

alist[k], alist[k-1] = alist[k-1], alist[k]


But we can do better even then this - we don't need to do all these swaps at all. Instead, find where the last element should go, and put it directly there. This is exactly the type of job the bisect module is good for: 

candidate = alist.pop()
bisect.insort(alist, candidate)


And this replaces the whole second while loop. 



So so far we have:

def insertionsort(alist):
    # work on a copy instead of the original
    alist = alist[:]

    if len(alist) &gt; 2:            
        alist[:-1] = insertionsort(alist[:-1])

    candidate = alist.pop()
    bisect.insort(alist, candidate)

    return alist

A = [4, 1, 6, 3, 9, 10]
A = insertionsort(A)

print(A)


I said before that copying is potentially bad for performance (each copy takes time). And we're doing a lot of it. This line:

alist[:-1] = insertionsort(alist[:-1])


makes a new list containing all but the last element, which the recursive call will promptly clone (in its entirety). So that's two copies for each element after the second. It would be better if we could tell the recursive call to only treat up to a certain point in the list, and everything after that. To do this, we put the bulk of the code into a helper function:

def insertionsort(alist):
    def sort_helper(alist, hi):
        if hi &gt; 1:            
            sort_helper(alist, hi-1)

        candidate = alist.pop(hi)
        bisect.insort(alist, candidate, hi=hi)

    alist = alist[:]
    sort_helper(alist, len(alist)-1)
    return alist

A = [4, 1, 6, 3, 9, 10]
A = insertionsort(A)

print(A)


Note that the first condition changed from testing a length to testing a position, and that the helper function works completely in-place. This makes one copy, in the outer function. You can also change it back to an in-place sort like your original code by deleting two lines, and it will make zero copies. This is probably the best a recursive insertion sort can be.