Quicksort is one of the most efficient sorting algorithms and is based on the divideandconquer approach. It was developed by Tony Hoare in 1959 and is still commonly used today.
In this comprehensive guide, we will cover the following:
Table of Contents
Open Table of Contents
Overview of Quicksort
Quicksort is based on the divideandconquer approach for sorting an array. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two subarrays, according to whether they are less than or greater than the pivot. The subarrays are then sorted recursively. This continues until the base case of empty or singleelement arrays is reached, which are inherently sorted.
The steps for quicksort are:
 Select the pivot element
 Partition the array into two subarrays based on the pivot
 Recursively sort the subarrays
Some key properties of quicksort:
 Extremely efficient on average  O(n log n) time complexity
 Inplace sorting algorithm  only requires constant O(1) space
 Unstable sorting algorithm  doesn’t preserve order of equal elements
 Efficient for large data sets and complex sorts
 Can be slower than other sorts for small arrays
 Performance depends heavily on pivot selection
These characteristics make quicksort very fast for a variety of applications from sorting user data to complex machine learning algorithms.
Implementing Quicksort in Python
Let’s now go through a stepbystep implementation of the quicksort algorithm in Python.
1. Select the Pivot Element
There are different ways to choose the pivot:
 Always pick first, last, or random element
 Pick median of three random elements
 Pick median of first, middle and last elements
For simplicity, we will start with always picking the last element as the pivot:
def quicksort(arr):
# always use last element as pivot
pivot = arr[len(arr)  1]
2. Partition the Array
This involves iterating through the array and swapping elements such that those less than the pivot are placed before elements greater than the pivot.
We will use a pointer i
that increments left to right, while swapping elements less than the pivot to the front of the array.
def quicksort(arr):
pivot = arr[len(arr)  1]
i = 0
for j in range(len(arr)  1):
if arr[j] < pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[len(arr)1] = arr[len(arr)1], arr[i]
The final swap places the pivot element between the two partitions.
3. Recursively Sort Subarrays
We simply call quicksort recursively on the slices from 0 to i1 (left partition) and i+1 to the end (right partition).
def quicksort(arr):
# pivot selection and partition
quicksort(arr[0:i])
quicksort(arr[i+1:len(arr)])
Putting it all together, the full quicksort implementation is:
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr)  1]
i = 0
for j in range(len(arr)1):
if arr[j] < pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[len(arr)1] = arr[len(arr)1], arr[i]
quicksort(arr[0:i])
quicksort(arr[i+1:len(arr)])
return arr
We added a base case to handle empty or singleelement arrays to avoid infinite recursion.
Let’s test it on an example array:
arr = [4, 2, 7, 3, 1, 6]
print(quicksort(arr))
# Output: [1, 2, 3, 4, 6, 7]
It correctly sorts the sample array!
Pivot Selection and Partitioning
Choosing the final element as pivot is simple but not optimal. Better alternatives include:
Median of Three Method
Pick median of first, middle and last elements as pivot:
def quicksort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
if arr[0] < arr[mid]:
if arr[mid] < arr[len(arr)1]:
pivot = arr[mid]
else:
pivot = arr[0]
else:
if arr[len(arr)1] < arr[mid]:
pivot = arr[mid]
else:
pivot = arr[len(arr)1]
This reduces the chance of imbalanced partitions.
Random Pivot
Select a random index between 0 and length1 as the pivot:
import random
# inside quicksort()
pivot_idx = random.randint(0, len(arr)1)
pivot = arr[pivot_idx]
Randomness improves performance on already sorted or reversed arrays.
For partitioning, instead of swapping, we can keep track of the boundary point and only swap once. This reduces expensive swap operations.
def partition(arr, pivot):
i = 0
for j in range(len(arr)):
if arr[j] < pivot:
arr[j], arr[i] = arr[i], arr[j]
i += 1
arr[i], arr[len(arr)1] = arr[len(arr)1], arr[i]
return i
Careful pivot selection and partitioning improves efficiency and avoids worstcase O(n^2) performance.
Time and Space Complexity Analysis
Time Complexity
 Best case: O(n log n)  pivot divides array into equal halves
 Average case: O(n log n)
 Worst case: O(n^2)  already sorted, or bad pivot selection
Quicksort is very efficient on average. But worstcase occurs with poor pivots.
Space complexity
Quicksort sorts inplace requiring only O(log n) space for recursion stack.
Optimizations and Improvements
Some optimizations to further improve quicksort:
 Use insertion sort for smaller arrays
 Switch to heapsort if recursion depth exceeds limit
 Track duplicates and equal elements
 Parallelize using multithreading
 Use 3way partitioning scheme
These optimizations make quicksort faster and more robust in different scenarios.
Comparison with Other Sorts
Merge Sort
 O(n log n) average and worstcase
 Stable sort
 O(n) extra space complexity
Merge has better worstcase but requires more space. Useful if stability is needed.
Heap Sort
 O(n log n) time
 Space O(1)
 Slower than quicksort in practice
Good alternative if quicksort’s worstcase is unacceptable.
Intro Sort
 Quicksort + fallback to heapsort
 Good hybrid algorithm
Introsort combines advantages of both quicksort and heapsort.
So quicksort is preferred in most cases, but alternatives have tradeoffs to consider.
Usage Examples and Applications
Quicksort is extensively used due to its excellent performance:
 Sorting small and large arrays/lists
 Ordering machine learning datasets
 Sorting user data in applications
 Graph algorithms like finding strongly connected components
 Database systems
 CPU cache optimizations
It’s one of the most popular sorting algorithms used in practice across domains.
Exercises
Some practice questions to test your quicksort skills:

Implement quicksort with a random pivot and hoare partitioning scheme.

Track the number of comparisons and swaps your quicksort algorithm makes.

Modify quicksort to detect and handle duplicate elements.

Combine quicksort with insertion sort to create a hybrid algorithm.

Implement 3way quicksort partitioning.
Conclusion
In this comprehensive guide, we implemented quicksort in Python from scratch, discussed key concepts like pivot selection and partitioning schemes, analyzed complexity, compared tradeoffs with other sorts, saw realworld applications, and worked through examples.
Quicksort is one of the fastest sorting algorithms due to its excellent divideandconquer approach. With some careful optimizations, it can be made even faster and adaptable for all kinds of sorting problems. Understanding quicksort provides a solid foundation in algorithmic thinking that is applicable across technical domains.
The implementation techniques, analysis, optimizations and examples covered in this guide will help prepare you for technical interviews. Quicksort remains a popular interview topic and being thorough with its concepts will give you an edge.
There are always opportunities to enhance the quicksort algorithm further through multithreading, cache optimizations, hybrid schemes and more. I hope this guide provided a comprehensive overview and starting point for mastering quicksort in Python.