# Quick sort in Python

How can this be improved?

def quick_sort(temp_list):
#Check if the array is having one element or not
if len(temp_list) == 1:
return temp_list
elif len(temp_list) >= 2:
l_list = list()
g_list = list()
#Choose a pivot
if len(temp_list) % 2 == 0:
pivot = temp_list[len(temp_list)/2 - 1]
else:
pivot = temp_list[len(temp_list)/2]
#Make two list greater and lesser than the pivot
for e in temp_list:
if e < pivot:
l_list.append(e)
elif e > pivot:
g_list.append(e)
#Merge the two list with the pivot
return merge(quick_sort(l_list),pivot,quick_sort(g_list))

def merge(list1,mid,list2):
newlist = list()
if not list1 and list2:
newlist.append(mid)
newlist.extend(list2)
if not list2 and list1:
newlist.extend(list1)
newlist.append(mid)
if list1 and list2 :
newlist.extend(list1)
newlist.append(mid)
newlist.extend(list2)
return newlist


# On Style

• “Quicksort” is customarily written as one word – the method should be called quicksort, not 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.

• Names: l_list and 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 lesser and 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”?

# Code

• Use the idiomatic [] instead of list() to initialise lists.

• The first elif is unnecessary, and causes the subsequent code to be indented too much. Remove it. (Also, it should logically be an else, not an elif).

• 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

import itertools

def sort(a):
def swap(i, j):
tmp = a[i]
a[i] = a[j]
a[j] = tmp

if len(a) < 2:
return a

lesser = []
greater = []
# Swap pivot to front so we can safely ignore it afterwards.
swap(0, len(a) // 2)
pivot = a[0]

# Invariant: lesser < pivot <= greater
for x in itertools.islice(a, 1, None):
if x < pivot:
lesser.append(x)
else:
greater.append(x)

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:

1. in-place partitioning along a pivot
2. 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.

Some changes to your code, First, your code didn't handle the case of empty list very well. This was why you need a complicated merge. (Also, the operation is not really a merge. A merge kind of means interleaving.)

def quick_sort(temp_list):
if len(temp_list) <= 1: return temp_list
pivot = temp_list[len(temp_list)/2 - (1 if len(temp_list) % 2 == 0 else 0) ]
l_list = list()
g_list = list()


by keeping a list of values equal to pivot, you can ensure that your sort works even if there are non unique values.

    m_list = list()
for e in temp_list:
if e < pivot:
l_list.append(e)
elif e > pivot:
g_list.append(e)
else:
m_list.append(e)
return concat([quick_sort(l_list),m_list,quick_sort(g_list)])

def concat(ll):
res = list()
for l in ll: res.extend(l)
return res

print quick_sort([8,4,5,2,1,7,9,10,4,4,4])

• Quicksort isn’t necessarily in-place, and it never has constant space requirement. – stackoverflow.com/a/4105155/1968 – Konrad Rudolph Jun 20 '12 at 11:45
• @KonradRudolph thanks, I removed that line. – rahul Jun 20 '12 at 12:12