“Quicksort” is customarily written as one word – the method should be called
quick_sort. What’s more, this is an implementation detail and a public API shouldn’t reveal this (it’s subject to change), hence
sort would be an even better name.
Some of your comments are redundant: “Check if the array is having one element or not” – that is (and should be!) obvious from the code. Don’t comment here. Reserve comments to explain why you do something. The next comment (“choose a pivot”) is better since that’s not immediately obvious from the code. However, it would be better to make it obvious in code and maybe have a comment describe how you choose the pivot (e.g. simple median).
The other comments are redundant again.
Furthermore, indenting the comments to the correct level would increase readability. As it stands, the comments visually hack the code into pieces.
g_list contain unnecessary information that would easily be inferred from context –
list, and their actual function is codified in just one letter. Rename them to
greater or similar.
temp_list as a parameter is actually wrong: it’s not really temporary, it’s just the input. And again,
list is a bit redundant. In fact, a one-letter identifier is acceptable here (but that’s the exception!). How about
a for “array”?
Use the idiomatic
 instead of
list() to initialise lists.
elif is unnecessary, and causes the subsequent code to be indented too much. Remove it. (Also, it should logically be an
else, not an
Your choice of the pivot is a bit weird. Why two cases? Why not just use the middle?
pivot = a[len(a) // 2]
Your code discards duplicate elements:
quick_sort([1, 2, 3, 2]) will yield
[1, 2, 3].
blufox has already remarked that your
merge routine is more convoluted than necessary. In fact, you could just use concatenation here,
lesser + [pivot] + greater (but this again discards duplicates)
It’s also a good idea to explicitly comment invariants in such algorithmic code.
Putting It Together
def swap(i, j):
tmp = a[i]
a[i] = a[j]
a[j] = tmp
if len(a) < 2:
lesser = 
greater = 
# Swap pivot to front so we can safely ignore it afterwards.
swap(0, len(a) // 2)
pivot = a
# Invariant: lesser < pivot <= greater
for x in itertools.islice(a, 1, None):
if x < pivot:
return sort(lesser) + [pivot] + sort(greater)
Bonus: Algorithmic Considerations
As blufox noted, this implementation requires more additional memory than necessary. This is acceptable when working with immutable data structures, but becomes quite expensive when used with mutable arrays.
A normal, mutable quicksort implementation consists of two steps:
- in-place partitioning along a pivot
- recursive sorting of the two partitions
The second step is trivial; the partitioning and choice of pivot however require some sophistication, otherwise they will have degenerate worst cases (even without considering the worst-case input “sorted array”). The definitive paper in this regard is Engineering a sort function by Bentley and McIlroy. It is one of the clearest, most thorough computer science papers ever written and I heartily recommend its reading.
That said, no “toy” implementation will ever replace an industry-strength implementation and attempting to do so is largely a waste of time, so it’s entirely reasonable to deliberately simplify an implementation by ignoring some performance considerations.
In this regard the implementation above fares quite well. Just for the gained understanding I would still suggest that you attempt writing a variant which uses an in-place partitioning step.