Should I use this very short Python Quicksort implementation?

``````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.

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(n2). 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.

• +1. This isn't quicksort, because the main improvement quicksort offers over other logarithmic sort methods (eg mergesort) is the ability to operate in-place. This is an implementation of the redesign of quicksort usually used in immutable functional languages, but frankly mergesort is better for this purpose in most cases anyway. Jul 5, 2016 at 6:48