QuickSort is one of the most famous sorting algorithms in computer science. I implemented the QuickSort in Python using two approaches including Recursive QuickSort and Iterative QuickSort.
The implementation were done in Python to explore a different approach than the traditional C and Java languages. Finally I scored the average running time obtained by running multiple times each approach.
The following are the system configurations used for benchmarking:
Python version: 2.7.5
Operating System: OS X 10.9.4
RAM Memory: 8GB
Processor 2.4 GHz Intel Core i5
Recursive QuickSort Python
The recursive quick sort version of this algorithm was implemented using the traditional divide and conquer paradigm: First choose a pivot (first element of the list in this case) and move all elements lower than the pivot to the left or elements greater than the pivot are move to the right. Then continue sorting the left side and the right side This algorithm is expected to have an average performance of the order of (N log N) the worst case of the order of (N2). The performance of this algorithm can be affected by selection of the pivot for the partition. As the input used for this benchmark in a randomly unsorted list the selection of the pivot is not an issue.
Figure 1 shows the log-log plot of the running time as a function of the input size. In this plot it can be seen that the implementation of the algorithms is running as expected. The plot shows a linearithmic order of grow of the function.
Some issues to note about this approach that the recursive calls can take a lot of stack overhead. In the case of Python, the random numbers in the input list varies from 1 to 10000. However, if the program only tries to sort lists where the random numbers are from 1 to 10 the program has a RuntimeError as the maximum recursion depth is exceed. When this is the case the Iterative method is recommended.
Iterative QuickSort Python
For the iterative version of the QuickSort algorithm a Stack was utilised to store elements when partitioning.
The running time of the implementation satisfy the expected result. When referring to Figure 2 it can be seen than the running time as a function of the input size is a linearithmic (N log N).
As this method is iterative there was no issues related to the input number as it was the case of the recursive versions.
When comparing both implementation of the algorithms there is not much difference in the running time. However, when these implementations were compared to the Python built in sort function running time there is some constant difference. For instance, for an input of 1 million elements Python’s sort function was 5 time faster. Python running time was just under a second and my implementation was around 5.5 seconds. Refer to figure 3
The following is the python code I wrote for this implementations.
QuickSort Implementations Recursive & Iterative
def quick_sort_iterative(list_, left, right):
Iterative version of quick sort
temp_stack = 
#Main loop to pop and push items until stack is empty
pos = temp_stack.pop()
right, left = pos, pos
piv = partition(list_,left,right)
#If items in the left of the pivot push them to the stack
if piv-1 > left:
#If items in the right of the pivot push them to the stack
if piv+1 < right:
def quick_sort_recursive(list_, left, right):
Quick sort method (Recursive)
if right <= left:
piv = partition(list_, left, right)
#Sort left side of pivot
quick_sort(list_, left, piv-1)
#Sort right side of pivot
quick_sort(list_, piv+1, right)
def partition(list_, left, right):
#Pivot first element in the array
piv = list_[left]
i = left + 1
j = right
while i <= j and list_[i] <= piv:
while j >= i and list_[j] >= piv:
if j <= i:
list_[i], list_[j] = list_[j], list_[i]
#Exchange pivot to the right position
list_[left], list_[j] = list_[j], list_[left]
Running times as a function of the input size (tines in milliseconds):