Quick Sort Algorithm in Python

Quicksort, aka partition-exchange sort, is a divide-and-conquer algorithm. It’s an efficient algorithm that takes O(nlogn) time to sort n items (on average). In the worst case, it might take O(n2) time.
Quicksort first divides a large list/array into two smaller sub-arrays using a pivot value – one with elements smaller than the pivot element and the other with elements larger than the pivot element. Unlike merge sort, it doesn’t wait for the list size to be 1 before starting the sorting process. Sorting is done during partition, which makes the combining of the sub-lists easier.

The steps are:
1. Pick an element, called a pivot, from the list/array.
2. Reorder the list/array so that all elements smaller than the pivot element come before the pivot, while all elements greater than the pivot element come after it (equal values can go either way. In my implementation, I have kept the pivot element on the lower side).
3. The above process is applied recursively with a list of size zero or one as the base case.

The Python code for the quicksort is as follows…

def quicksort(a,low,high):
	if (low < high):
		p = partition(a,low,high)   # get pivot
		quicksort(a,low,p)      # apply quick sort on smaller elements
		quicksort(a,p+1,high)	# apply quick sort on larger elements
	return a

def partition(a,lo,hi):
	pivot = a[hi-1]
	i = lo
	for j in xrange(lo, hi-1):
		if (a[j] <= pivot):
			x = a[i]
			a[i] = a[j]
			a[j] =x
			i = i+1
	y = a[i]
	a[i] = pivot
	a[hi-1] = y
	return i

l = [13,18,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]
final = quicksort(l,0,len(l))	
print "sorted list is ", final

The output of the above code looks like this..

sorted list is  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 13, 14, 15, 16, 18]