Should I use this very short Python Quicksort implementation?

Question

def quicksort(N):
    if len(N) < 2:
        return N
    else:
        less = quicksort([number for number in N[1:] if number < N[0]])
        more = quicksort([number for number in N[1:] if number >= N[0]])

    return sum([less, [N[0]], more], [])

print(quicksort([1, 9, 6, 10, 8, 7, 2, 4, 3, 5]))

It seems to work, but I'm not sure if it's as technically adequate than other longer variants of implementation.

Answer 1

I am assuming you are aware of Python's built-in sort and are simply asking this as a learning exercise. (If you just want to use the 'best' sort, use Python's built-in sort function. It is heavily optimised and will be faster than anything you implement in Python.)

The short answer is, your quicksort function has a bug, and if you fix it then it will work as expected. However there are other things to consider.

The bug

The code does not work correctly when there are several elements in the array which are equal to N[0]. Try quicksort([1,2,1,1]).

Performance

Although the asymptotic (big-O) complexity is the same as a standard quicksort, the performance of this code will be reduced due to:

• Lots of creation of new lists (Quicksort can be easily designed to not require any memory allocation)
• Scanning through the list twice rather than once

Try timing your implementation versus another one (use the timeit module). Make sure to try large input lists.

Also, quicksort algorithms have a worst-case complexity of O(n²). If you want a worst-case complexity of O(n log n) you should consider Mergesort, which can also be implemented with very short code.

Clarity

Why

return sum([less, [N[0]], more], [])

when you can simply do:

return less + [N[0]] + more

Note that in either case, this still involves the creation of new lists, so the performance could be further improved, probably at the expense of clarity.