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 code does not work correctly when there are several elements in the array which are equal to
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.
return sum([less, [N], more], )
when you can simply do:
return less + [N] + 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.