python quicksort - Can this code be improved?

Question

Can you give me advice about how to improve this code?

def qsort(arr):
    if len(arr) < 2:
        return arr
    else:
        root =  arr[round(len(arr)/2)]
        arr.remove(root)
        min_  = [i for i in arr if i <  root]
        max_  = [i for i in arr if i >  root]
        oth_  = [i for i in arr if i == root]
        return  qsort(min_) + [root]+oth_ + qsort(max_)

Answer 1

I can think of two things that may improve the efficiency of this code. The first is to use one loop with the three i < root, i > root, and i == root conditions as if/elif/else statements as the body instead of using list comprehension for each condition. That will cut down the amount of times you are touching each element of the array from around 3 to around 1.

The second thing is deleting the root from the array. You don't accomplish too much by doing this (you could just get the root index and reference arr[root_index] whenever you need the root), and removing an element from the middle of an array can be somewhat of a costly operation in Python (since you're not getting the index, you are actually searching the array for the root again, then deleting it, then shifting everything in an index higher than the root down an index). Remember not to double count it though if you decide not to remove it from the array.