# Recursive Quick Sort in Python

Fri 23 March 2007 by Thejaswi Puthraya## Recursive Quick Sort Algorithm in Python

Well it has been a long time since I blogged about algorithms (my last post on alogrithms here). As promised I am back with the quicksort algorithm. The quicksort alogrithm that I've written is recursive in nature against the iterative implementation.

Though the iterative implementation is efficient because there is a lower memory overhead as compared to its recursive implelementation, it is very complex to code (though not impossible).

The recursive alogorithm on the other hand consumes a lot of stack space and has a considerable overhead for the subsequent recursive calls. I would recommend Wikipedia as a great resource on algorithms. You can check out this link to know more about algorithms.

Here is the code I've written:

```
q=[]
def quicksort(q):
lesser=[]
greater=[]
if len(q) <= 1:
return q
for i in q[1:]:
if i < q[0]:
lesser.append(i)
else:
greater.append(i)
return quicksort(lesser)+q[0:1]+quicksort(greater)
```

Here is the benchmarking result that I've obtained:

### Results of Quicksort

Number of Elements | |||||||

in seconds | 10 |
50 |
100 |
200 |
500 |
1000 |
5000 |

Quicksort | 0.086 | 0.373 | 0.781 | 2.196 | 5.393 | 9.855 | 95.567 |

Compare with Bubble Sort and Straight Insertion Sort benchmark results.

The mere fact that the quicksort algorithm executes in micro seconds shows its speed. Thanks to C.A.R.Hoare for developing such a fast algorithm.